최대 합 증가 부분 수열

최대 합계 증가 하위 시퀀스는 합계가 최대이고 하위 시퀀스에서 모든 요소가 오름차순으로 정렬되는 주어진 정수 목록의 하위 시퀀스입니다.

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