1760:最大数字子串TimeLimit:1500msMemoryLimit:10000kBJudgetype:Multi-casesTotalSubmit:1215(245users)AcceptedSubmit:397(209users)PageView:6115FontStyle:AaAaAa输入n(1<=n<=1e6)和n个整数,这n个整数的绝对值均小于1000,求最大数字子串之和。Input输入为多组样例数据,每组第一行为一个正整数n,第二行为n个整数组成的数字串。Output对于每组样例,输出仅为一行,表示最大数字子串的各项之和。SampleInput9-3492-10-7113-813-126-35-714-5-1518-49SampleOutput1517Hint在第一组中,最大的数字子串是492的和在第二组中,最大的数字子串是26-35-714的和./:-3492-10-7113-8记录方法:-3413155-711146把当前的最大和(含当前末尾的最大和)记录下来,虽然不能直接得出最大和是多少,但可以进行遍历搜索最大值即可!?关键是要对负数处理好,看例二,最大子串含有负数。-126-35-714-5-1518-49-128?如果在此处断开记录-3,那么前面的2,6两个正数就和后边断开了,实际上2+6+(-3)>0,如果后边是正数的话,完全可以加上这3个数(比如后边的5)-128510?相同处理:-**********?后面是-15,加上12(前面的子串能形成的最大和)也小于0,所以此处应该断开了!记录-15!最后-**********-1518413?输入数组a[i],用数组s[i]记录最后一个数为a[i]时的最大子串和?状态转移方程为?s[i]=max(s[i-1]+a[i],a[i]);1<=i<n-1?初始条件s[0]=a[0]?然后s[i]中最大元素即为所求。AC代码:?#include<>?inta,s;?intmain()?{?inti,n,num;?while(~scanf("%d",&n)){?scanf("%d",&s);?num=s;?
动态规划_最大子序列 来自淘豆网m.daumloan.com转载请标明出处.
