最大总和增加子序列

最大总和增加子序列是给定整数列表的子序列，该整数列表的总和为最大，并且在该子序列中，所有元素均按升序排序。

假设有一个数组来存储最大和增加子序列，使得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