最大合計増加部分列

Maximum Sum Increasingサブシーケンスは、指定された整数のリストのサブシーケンスであり、その合計は最大であり、サブシーケンスでは、すべての要素が昇順で並べ替えられます。

L [i]が配列[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