Chuỗi con tăng tổng số tối đa | DP-14 trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm Thứ tự con tăng tổng số tối đa.

Đối với điều này, chúng ta sẽ được cung cấp một mảng chứa N số nguyên. Nhiệm vụ của chúng ta là chọn các phần tử từ mảng thêm vào tổng tối đa sao cho các phần tử có thứ tự được sắp xếp

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//returning the maximum sum
int maxSumIS(int arr[], int n) {
   int i, j, max = 0;
   int msis[n];
   for ( i = 0; i < n; i++ )
      msis[i] = arr[i];
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if (arr[i] > arr[j] &&
            msis[i] < msis[j] + arr[i])
            msis[i] = msis[j] + arr[i];
      for ( i = 0; i < n; i++ )
         if ( max < msis[i] )
            max = msis[i];
         return max;
}
int main() {
   int arr[] = {1, 101, 2, 3, 100, 4, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Sum of maximum sum increasing subsequence is "<<
   maxSumIS( arr, n ) << endl;
   return 0;
}

Đầu ra

Sum of maximum sum increasing subsequence is 106