要知道，最大和最小是相对的，用总和减去最小的就能得到最大的。 编程之美的题目没看懂，然后参考了http://zhangpeizhen.blog.163.com/blog/static/231873112201431784024921/
两种情况
1、普通数组，可以o(n)求最大子串和。
2、如果是环状，那么则要看到跨越 n-1 到 0 的这段环状的情况，要求这段最大的和，只需要用总和减去非环状的最小子串和即可。
然后取两种情况的最大值即可。
#include#include #include #include #include using namespace std;void dp() { int i,t1,t2; t1 = arra[0]; t2 = arra[0]; Max = t1; Min = t2; for( i = 1 ; i < n ; i ++) { if(t1 <= 0) t1 = arra[i]; else t1 += arra[i]; if(t2 >= 0) t2 = arra[i]; else t2 += arra[i]; Max = max(t1,Max); Min = min(t2,Min); } Max = max(Max,total-Min); printf("%d\n",max(Max,0));} int main() { while(~scanf("%d",&n)) { total = 0; for(int i = 0 ; i < n ; i ++) { scanf("%d",&arra[i]); total += arra[i]; } dp(); } return 0;}
但是我觉得少考虑了一种情况，比如全部为-1的数组，
普通数组最大子串和为-1，
按照上面求的最大的环状的必然为0，但是这样就是什么都不取的状态，
所以我觉得最后需要判断 是否 最小子串和 与 整个数组和 相等，如果相等说明就是上面考虑的情况，那么就取普通数组的的最大子串和就行了。