給定一組數，有正有負，求連續的幾個數之和的最大值？并求出是從第幾個數開始，第幾個數結束？如果有多個序列可組成相同的最大值，則選取最開始的一個序列。（注：這兩天看《編程之美》，發現2.14節，求數組的子數組之和的最大值，跟這個題十分相似，但是沒有要求求出開始喝結束的位置，只要求求出最大值，解題思路跟下面的代碼相似，但只用了兩個變量，沒有用數組，做到時間復雜度O（n），空間復雜度O（1））
用程序設計實現。我實現了一種方法，跟大家分享一下，如果朋友你有更好的方法來解決這個問題，希望你能回復，與大家分享一下。
另外，如果題目改成：“給定一組數，有正有負，求連續的幾個數之和的最大值？并求出是從第幾個數開始，第幾個數結束？如果有多個序列可組成相同的最大值，則選取序列中數字最少的那個。”該怎么寫程序，本人思考良久沒有想到好的辦法。求指點！！！！！！！
下面是我實現的C++代碼：
#include "stdafx.h"
#include <iostream>
using namespace std;
int GetMaxs(int arrary[],const int n)
{
int max = 0, temp = 0; //max最大值，temp臨時變量
int begin = 0, end = 0;
int *maxlist= new int[n]; //maxlist[n],一個數組，跟原數組一般大
max = maxlist[0] = arrary[0];
begin = end = arrary[0];
for (int i = 1; i < n; i++)
{
temp = maxlist[i - 1] + arrary[i];
if (temp > arrary[i])
{
maxlist[i] = maxlist[i - 1] + arrary[i]; //更新最大值數組
}
else
{
maxlist[i] = arrary[i]; //更新最大值數組
}
if (maxlist[i] > max)
{
max = maxlist[i]; //用當前值更新最大值
end = i; //設置終點索引
}
}
//下面幾句是尋找起始點
int j = end, sum = 0;
while (j < n && sum != max )
{
sum += arrary[j];
j --;
}
begin = ++j;
cout << "The max sum is: " << max << endl;
cout << "The begin position is: " << ++begin << endl;
cout << "The end position is: " << ++end << endl;
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
//int a[] = {-1,-1,-1,1,1,1,-1,-1,-1,-1,1,1,-1,1,1,-1};
int a[] = {5,8,12,-25,-15,56,-14,25,2,-10,6};
int n = sizeof(a)/sizeof(a[0]);
GetMaxs(a,n);
return 0;
}
另外一道很相似的題目：有一個數組a[n]，里面的數只有兩種：-1和1。 i、j是兩個整數，假設0 <= i < j <= n -1 ,找出a[i]到a[j]中連續數之和最大的部分（如果最大部分存在相等，則優先找最短的）。
這道題和上面的題類似，只不過本人還是想不出怎么取最短，只做到取首次取得最大值。
