其實這個題目也很簡單 有很多種做法...
就是給一個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 ----- */