資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中從字首和給定元素之後的字首的最大和遞增子序列
在這個問題中，我們給定一個包含N個整數的陣列arr[]以及兩個索引值x和y。我們的任務是建立一個程式，用C++查詢從字首到給定元素之後的字首的最大和遞增子序列。
問題描述
我們將找到直到索引x且包括索引y處的元素的遞增序列的最大和。
讓我們來看一個例子來理解這個問題：
輸入
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6輸出
26
解釋
我們將取直到索引3的子序列，然後最後包含arr[6] = 11。
子序列是{1, 5, 9, 11}。和 = 1+5+9+11 = 26
解決方案方法
一種簡單的方法是建立一個直到索引x的新陣列，然後在末尾新增索引y處的元素。然後計算所有遞增子序列，然後丟棄所有不能包含元素arr[y]的子序列，並找到maxSum。
另一種有效的方法是使用動態規劃方法。其思想是建立一個二維陣列DP[][]，並存儲遞增子序列的最大和。DP[x][y]的值將給出直到索引x且包括元素arr[y]的最大和。
示例
程式演示了我們解決方案的工作原理：
#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<DP[x][y];
return 0;
}輸出
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
一種**有效的方法**是找到直到索引x的遞增子序列的最大和，使得序列的最大元素小於索引y處的元素。為此，我們將再次使用動態規劃方法。
示例
程式演示了我們解決方案的工作原理：
#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
}輸出
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
更新於：2020年10月15日
106 次瀏覽
廣告