# 最大總和增加子序列| DP-14 > 原文： [https://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/](https://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/) 給定 n 個正整數數組。 編寫程序以查找給定數組的最大和子序列的總和，以使子序列中的整數按升序排序。 例如，如果輸入為{1、101、2、3、100、4、5}，那么如果輸入數組為{3、4，則輸出應為 106（1 + 2 + 3 + 100）。 5，10}，則輸出應為 22??（3 + 4 + 5 + 10），如果輸入數組為{10，5，4，3}，則輸出應為 10 **解決方案** 此問題是標準[最長子序列（LIS）問題](https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/)的變體。 我們需要對 [LIS 問題](https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/)的動態編程解決方案進行一些更改。 我們需要更改的只是使用總和作為標準，而不是增加子序列的長度。 以下是該問題的動態編程解決方案： ## C++ ```cpp /* Dynamic Programming implementation? of Maximum Sum Increasing Subsequence? (MSIS) problem */ #include <bits/stdc++.h> using namespace std; /* maxSumIS() returns the maximum? sum of increasing subsequence? in arr[] of size n */ int maxSumIS(int arr[], int n)? {? ????int i, j, max = 0;? ????int msis[n];? ????/* Initialize msis values? ????for all indexes */ ????for ( i = 0; i < n; i++ )? ????????msis[i] = arr[i];? ????/* Compute maximum sum values? ????in bottom up manner */ ????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];? ????/* Pick maximum of? ????all msis values */ ????for ( i = 0; i < n; i++ )? ????????if ( max < msis[i] )? ????????????max = msis[i];? ????return max;? }? // Driver Code? 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;? }? // This is code is contributed by rathbhupendra ```