最大子串问题

最大子串和解决的最大的连续子串问题,例如我们得到如下一段子串

-2 1 -3 4 -1 2 1 -5 4

我们要找出这些数的最大连续子串,我们算法的思想是一个一个添加,从头开始添加,我们把情况定位2种情况,上一段最大子串和+当前字符串和当前字符串进行比较,取最大值,数学公式是:

max{上一段最大子串+当前数值,当前数值}

那么我们以上面的数据来举例计算,计算方式如下:

-2 max{-2+1,1}=1 max{1+-3,-3}=-2max{-2+4,4}=4 max{4+-1,-1}=3

max{3+2,2}=5 max{5+1,1}=6 max{6+-5,-5}=-1 max{1+4,4}=5

我们可以得出结果,上面这一串数据的最大子串和是6 在4 -1 2 1 这一段数据中,在我们程序中,可以记录下这些,但我们要的是最大子串和,所以我们也可以在计算过程中只取最大子串和。下面是我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
int main()
{
int a[9]={-2,1,-3,4,-1,2,1,-5,4},max,final_max=-99999;
for(inti=0;i<9;i++)
{
if(i==0)max=a[0];
else{
max=max+a[i]>a[i]?max+a[i]:a[i];
}
if(max>final_max)final_max=max;
}
printf("%d",final_max);
return 0;
}