一个字符串的问题！急求！

anthony1983

固定长度的话，更加简单，不用分治法也能解决了，时间复杂度为O(n)

int MaxSumSequence(int *a, int size, int seq) //获得序列的下标 {     if (seq >= size)         return 0;  //下标     int i,j, sum=0, temp=0, pos = 0;     for (i=0; i<seq; i++)         sum+=a[i];     temp = sum;     for (i=seq; i<size; i++)     {         temp +=a[i]-a[i-seq]; //计算所有长度为3的邻近序列和         if (temp > sum)         {             pos = i-seq+1;             sum = temp;  //每次记录最大的         }     }     return pos; } int _tmain(int argc, _TCHAR* argv[]) {     int    test[] = {1,2,3,-3,-4,5,6,-1,3,4,7,-9,10,-1,2};     cout << MaxSumSequence(test, sizeof(test)/sizeof(int), 3) << endl; }

[ 本帖最后由 anthony1983 于 2007-12-3 11:43 编辑 ]