其實(shí)這個(gè)題目也很簡(jiǎn)單 有很多種做法...
就是給一個(gè)array你 然后你找出 i,j使從第i個(gè)加到第j個(gè)最大就好了啊
最簡(jiǎn)單的算法就是兩個(gè)for 算下來(lái)不到n^2的時(shí)間復(fù)雜度 可是還有更快的算法哦
首先 可以使用分治算法 這樣的算法大概時(shí)間復(fù)雜度是 n*lg n， 但是這樣還不是最好的
最好的其實(shí)是把前一個(gè)狀態(tài)儲(chǔ)存下來(lái)然后進(jìn)行比較 這個(gè)算法時(shí)間復(fù)雜度只有n哦 很快的呢
先不要看 給個(gè) 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 ----- */