经典的动态规划问题:
解决问题的关键在于dp[i]数组的定义
#include <iostream> using namespace std; #define MAXN 1000001 #define MIN -999999 int main(){ long long dp[MAXN]={MIN};//dp[i]表示包括数组中包含第i个即A[i-1]的最大序列和 long long A[MAXN]={0}; long long N=0; long long res=MIN; while(cin>>N){ res=MIN; for(int i=1;i<=N;i++){ cin>>A[i]; } for(int i=1;i<=N;i++){ dp[i]=max(A[i],A[i]+dp[i-1]); res=max(res,dp[i]); } cout<<res<<endl; } return 0; }