一、最大连续子序列
1.题目叙述
对于一个数字序列A1A2A3...An,求出连续子序列的最大和，如对于序列-2,11，-4,13，-5，-2，其中的最大序列和是11+（-4）+13=20
2.动态规划解法
将问题拆分成子问题，即dp[i]表示以A[i]为结尾的子序列的最大和，最后对于这些dp数组找出最大值即可，状态转移方程为：
dp[i] = max{ dp[i-1] + A[i] } 状态dp[i]表示，当前以A【i】结尾的子序列的最大和
3.方法一是经典算法，方法二是根据状态方程优化而来。
#include<iostream>
#include<algorithm>
using namespace std;
int maxSum1(int arr[],int n){
int dp[10];
int ans = INT32_MIN;
dp[0] = arr[0];//初始化
for(int i=1;i<n;i++){
dp[i] = max(dp[i-1]+arr[i], arr[i]);
ans = max(ans,dp[i]);
}
return ans;
}
int maxSum2(int arr[],int n){
int dp = arr[0];
int m = arr[0];
for(int i=1;i<n;i++){
if(dp<0){
dp = arr[i];
}
else dp+=arr[i];
if(dp>m){
m = dp;
}
}
return m;
}
int main(){
//-2,6,-1,5,4,-7,2,3
//dp[i] = max{dp[i-1]+A[i], A[i]}
int arr[8]={-2,6,-1,5,4,-7,2,3};
cout<<"algorithm 1: "<<maxSum1(arr,8)<<endl;
cout<<"algorithm 2: "<<maxSum2(arr,8)<<endl;
return 0;
}
二、最长不下降子序列（可以不连续）