动态规划最大子序列.doc

?1760: 最大数字子串 Time Limit: 1500 ms ?? Memory Limit: 10000 kB?? Judge type: Multi-casesTotal Submit : 1215?(245 users)???Accepted Submit : 397?(209 users)???Page View : 6115? Font Style: Aa Aa Aa 输入n(1=n=1e6)和n个整数，这n个整数的绝对值均小于1000，求最大数字子串之和。 Input 输入为多组样例数据，每组第一行为一个正整数n，第二行为n个整数组成的数字串。 Output 对于每组样例，输出仅为一行，表示最大数字子串的各项之和。 Sample Input 9 -3 4 9 2 -10 -7 11 3 -8 13 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 Sample Output 15 17 Hint 在第一组中，最大的数字子串是4 9 2的和在第二组中，最大的数字子串是2 6 -3 5 -7 14的和/p1760.html 方法： -3 4 9 2 -10 -7 11 3 -8 记录方法： -3 4 13 15 5 -7 11 14 6 把当前的最大和（含当前末尾的最大和）记录下来，虽然不能直接得出最大和是多少，但可以进行遍历有哪些信誉好的足球投注网站最大值即可！ 关键是要对负数处理好，看例二，最大子串含有负数。 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 -1 2 8 ？ 如果在此处断开记录-3，那么前面的2，6 两个正数就和后边断开了，实际上2+6+（-3）0，如果后边是正数的话，完全可以加上这3个数（比如后边的5） -1 2 8 5 10 ？ 相同处理： -1 2 8 5 10 3 17 12？ 后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此处应该断开了！记录-15！ 最后-1 2 8 5 10 3 17 12 -15 1 8 4 13 输入数组a[i],用数组s[i]记录最后一个数为a[i]时的最大子串和 状态转移方程为?? s[i]?=?max(s[i-1]+a[i],a[i]);?1=in-1?? 初始条件s[0]=a[0] 然后s[i]中最大元素即为所求。? AC代码： #includestdio.h int a, s; int main() { int i,n,num; while(~scanf(%d,n)){ scanf(%d,s); num=s; for(i=1;in;i++){ scanf(%d,a); if(s0) s=a; else s+=a; if(nums) num=s; } printf(%d\n,num); } return 0; } MLE代码： #includestdio.h int a[2000000],s[2000000]; int main() { int i,n,num; //num记录最大值 while(~scanf(%d,n)){ for(i=0;in;i++) scanf(%d,a[i]); num=s[0]=a[0]; for(i=1;in;i++) if(s[i-1]0) s[i]=a[i]; else s[i]=s[i-1]+a[i]; for(i=1;in;i++) if(nums[i]) num=s[i]; printf(%d\n,num); } return 0; }