資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究最大和遞增子序列\n
最大和遞增子序列是給定整數列表的一個子序列，其和最大且在子序列中，所有元素按升序排列。
假設有一個數組用於儲存最大和遞增子序列，其中 L[i] 是最大和遞增子序列，它以 array[i] 結尾。
輸入和輸出
Input:
Sequence of integers. {3, 2, 6, 4, 5, 1}
Output:
Increasing subsequence whose sum is maximum. {3, 4, 5}.演算法
maxSumSubSeq(array, n)
輸入：數字序列，元素數。
輸出：遞增子序列的最大和。
Begin define array of arrays named subSeqLen of size n. add arr[0] into the subSeqLen for i in range (1 to n-1), do for j in range (0 to i-1), do if arr[i] > arr[j] and sum of subSeqLen [i] < sum of subSeqLen [j], then subSeqLen[i] := subSeqLen[j] done done add arr[i] into subSeqLen[i] res := subSeqLen[0] for all values of subSeqLen, do if sum of subSeqLen[i] > sum of subSeqLen[res], then res := subSeqLen[i] done print the values of res. End
示例
#include <iostream>
#include <vector>
using namespace std;
int findAllSum(vector<int> arr) { //find sum of all vector elements
int sum = 0;
for(int i = 0; i<arr.size(); i++) {
sum += arr[i];
}
return sum;
}
void maxSumSubSeq(int arr[], int n) {
vector <vector<int> > subSeqLen(n); //max sum increasing subsequence ending with arr[i]
subSeqLen[0].push_back(arr[0]);
for (int i = 1; i < n; i++) { //from index 1 to all
for (int j = 0; j < i; j++) { //for all j, j<i
if ((arr[i] > arr[j]) && (findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j])))
subSeqLen[i] = subSeqLen[j];
}
subSeqLen[i].push_back(arr[i]); //sub Sequence ends with arr[i]
}
vector<int> res = subSeqLen[0];
for(int i = 0; i<subSeqLen.size(); i++) {
if (findAllSum(subSeqLen[i]) > findAllSum(res))
res = subSeqLen[i];
}
for(int i = 0; i<res.size(); i++)
cout << res[i] << " ";
cout << endl;
}
int main() {
int arr[] = { 3, 2, 6, 4, 5, 1 };
int n = 6;
cout << "The Maximum Sum Subsequence is: ";
maxSumSubSeq(arr, n);
}輸出
The Maximum Sum Subsequence is: 3 4 5
更新於： 2020 年 6 月 17 日
450 瀏覽
廣告