dp的一道经典题目;
很好理解:
#include<stdio.h> #include<string.h> int num[1000005]; int n; int getsum() { int max1=0,max2=0; for(int i=0; i<n; i++) { max1+=num[i]; if(max1>max2) max2=max1; if(max1<0) max1=0; } return max2; } int main() { //freopen("a.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d",&n); int mx=-101; for(int i=0; i<n; i++) { scanf("%d",&num[i]); if(mx<num[i]) mx=num[i]; } if(mx<0) printf("%d\n",mx); else printf("%d\n",getsum()); } return 0; }
这道题还有一个点,需要在以后过程中注意的就是数据,当数据全为负的时候的情况。