資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最大和遞增子序列 | C++ 中的 DP-14
在本教程中，我們將討論一個尋找最大和遞增子序列的程式。
為此，我們將使用一個包含 N 個整數的陣列。我們的任務是從陣列中選取元素，新增到最大和中，使得元素按升序排列
示例
#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;
}輸出
Sum of maximum sum increasing subsequence is 106
更新時間：2020 年 7 月 22 日
107 次瀏覽
廣告