其实这个题目也很简单 有很多种做法...
就是给一个array你 然后你找出 i,j使从第i个加到第j个最大就好了啊
最简单的算法就是两个for 算下来不到n^2的时间复杂度 可是还有更快的算法哦
首先 可以使用分治算法 这样的算法大概时间复杂度是 n*lg n， 但是这样还不是最好的
最好的其实是把前一个状态储存下来然后进行比较 这个算法时间复杂度只有n哦 很快的呢
先不要看 给个 int a[10] = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 }
求它的最大子串有多大哦
inline int
max( int a, int b)
{
return a > b ? a : b;
}
/*****************************************************************************
* This Function count a array find the largest string count max *
* Function : CountMax *
* int *a : the array of int *
* int n : the range of array *
* return : the sum of max this function find *
*****************************************************************************/
int
CountMax ( int *a, int n )
{
int sum = 0, tmp = 0;
for( int i = 0; i < n; i++ )
{
tmp = max( 0, tmp + a[i] );
sum = max( sum, tmp );
}
return sum;
}
/* ----- end of function CountMax ----- */