动态规划DP入门问题----最大连续子序列，最长不下降子序列（可以不连续），最长公共子序列

#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;
}