首页 > 代码库 > 环状数组最大子串和 最大和最小是相对的
环状数组最大子串和 最大和最小是相对的
要知道，最大和最小是相对的，用总和减去最小的就能得到最大的。 编程之美的题目没看懂，然后参考了http://zhangpeizhen.blog.163.com/blog/static/231873112201431784024921/
两种情况
1、普通数组，可以o(n)求最大子串和。
2、如果是环状，那么则要看到跨越 n-1 到 0 的这段环状的情况，要求这段最大的和，只需要用总和减去非环状的最小子串和即可。
然后取两种情况的最大值即可。
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<string>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，但是这样就是什么都不取的状态，
所以我觉得最后需要判断 是否 最小子串和 与 整个数组和 相等，如果相等说明就是上面考虑的情况，那么就取普通数组的的最大子串和就行了。
环状数组最大子串和 最大和最小是相对的
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。