在本教程中,我们将讨论一个寻找最大总和增加子序列的程序。
为此,我们将提供一个包含N个整数的数组。我们的任务是从数组中选取元素,这些元素的总和为最大,从而使元素按排序顺序排列
#include <bits/stdc++.h> using namespace std; //返回最大和 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; }
输出结果
Sum of maximum sum increasing subsequence is 106