ผลรวมสูงสุดที่เพิ่มขึ้นตามลำดับ

ผลรวมสูงสุด การเพิ่มลำดับย่อยเป็นผลสืบเนื่องของรายการจำนวนเต็มที่กำหนด ซึ่งผลรวมสูงสุดและในลำดับถัดไป องค์ประกอบทั้งหมดจะถูกจัดเรียงตามลำดับที่เพิ่มขึ้น

ให้มีอาร์เรย์เพื่อเก็บผลรวมสูงสุดที่เพิ่มตามลำดับ ดังนั้น 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