子串和
- 描述
- 给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1<=x<=y<=n。
- 输入
- 第一行是一个整数N(N<=10)表示测试数据的组数）
每组测试数据的第一行是一个整数n表示序列*有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000) - 输出
- 对于每组测试数据输出和最大的连续子串的和。
- 样例输入
-
1
5
1 2 -1 3 -2 - 样例输出
-
5
- 提示
- 输入数据很多,推荐使用scanf进行输入
-
又一个经典问题，对于一个包含负值的数字串array[1...n]，要找到他的一个子串array[i...j]（0<=i<=j<=n），使得在array的所有子串中，array[i...j]的和最大。
这里我们需要注意子串和子序列之间的区别。子串是指数组中连续的若干个元素，而子序列只要求各元素的顺序与其在数组中一致，而没有连续的要求。对于一个元素数为n的数组，其含有2^n个子序列和n(n+1)/2个子串。如果使用穷举法，则至少需要O(n^2)的时间才能得到答案。卡耐基梅隆大学的Jay Kadane的给出了一个线性时间算法，我们就来看看，如何在线性时间内解决最大子串和问题。
要说明Kadane算法的正确性，需要两个结论。首先，对于array[1...n]，如果array[i...j]就是满足和最大的子串，那么对于任何k(i<=k<=j)，我们有array[i...k]的和大于0。因为如果存在k使得array[i...k]的和小于0，那么我们就有array[k+1...j]的和大于array[i...j]，这与我们假设的array[i...j]就是array中和最大子串矛盾。
其次，我们可以将数组从左到右分割为若干子串，使得除了最后一个子串之外，其余子串的各元素之和小于0，且对于所有子串array[i...j]和任意k（i<=k<j），有array[i...k]的和大于0。此时我们要说明的是，满足条件的和最大子串，只能是上述某个子串的前缀，而不可能跨越多个子串。我们假设array[p...q]，是array的和最大子串，且array[p...q]，跨越了array[i...j]，array[j+1...k]。根据我们的分组方式，存在i<=m<j使得array[i...m]的和是array[i...j]中的最大值，存在j+1<=n<k使得array[j+1...n]的和是array[j+1...k]的最大值。由于array[m+1...j]使得array[i...j]的和小于0。此时我们可以比较array[i...m]和array[j+1...n]，如果array[i...m]的和大于array[j+1...n]则array[i...m]>array[p...q]，否array[j+1...n]>array[p...q]，无论谁大，我们都可以找到比array[p...q]和更大的子串，这与我们的假设矛盾，所以满足条件的array[p...q]不可能跨越两个子串。对于跨越更多子串的情况，由于各子串的和均为负值，所以同样可以证明存在和更大的非跨越子串的存在。对于单元素和最大的特例，该结论也适用。
根据上述结论，我们就得到了Kadane算法的执行流程，从头到尾遍历目标数组，将数组分割为满足上述条件的子串，同时得到各子串的最大前缀和，然后比较各子串的最大前缀和，得到最终答案。我们以array={−2, 1, −3, 4, −1, 2, 1, −5, 4}为例，来简单说明一下算法步骤。通过遍历，可以将数组分割为如下3个子串（-2），（1，-3），（4，-1，2，1，-5，4），这里对于（-2）这样的情况，单独分为一组。各子串的最大前缀和为-2，1，6，所以目标串的最大子串和为6。
以上摘自：http://blog.csdn.net/joylnwang/article/details/6859677
#include<stdio.h>
int main()
{
int n,m,i,fu,a,flag,sum,suma;
scanf("%d",&n);
while(n--)
{
fu=-111;flag=0;
sum=0;suma=0;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&a);
if(a<0)
fu=fu>a?fu:a; //考虑全为负数的情况
else
flag=1;
suma+=a; //对所分出的每一个子串进行求和
if(suma>0)
sum=sum>suma?sum:suma;
else
suma=0;
}
if(flag==1)
printf("%d\n",sum);
else
printf("%d\n",fu);
}
return 0;
}