第一次寫dp,有點小激動哈哈,紀念下
給定一個N個整數組成的序列,整數有正有負,找出兩段不重疊的連續子序列,使得它們中整數的和最大。兩段子序列都可以為空。
對於每組輸入,輸出一行,僅一個整數,表示最大的和。
9 185 -580 -889 701 964 -878 353 -761 608
2273
樣例輸入序列的一種選擇為:(701 964)和(608)
#include#include #include using namespace std; #define Max 1000002 int num[Max]; int dp1[Max],dp2[Max]; int main() { int n; freopen("input.txt","r",stdin); while( scanf("%d",&n)!=EOF) { memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); int sum=0; for(int i=1;i<=n;i++) { scanf("%d",num+i); int &temp=num[i]; dp1[i]=dp1[i-1]; if(sum<0)sum=temp; else sum+=temp; if(dp1[i] =1;i--) { int temp1=num[i]; dp2[i]=dp2[i+1]; if(sum<0)sum=temp1; else sum+=temp1; if(dp2[i]