#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],一個數(shù)組，跟原數(shù)組一般大
 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]; //更新最大值數(shù)組
  }
  else
  {
   maxlist[i] = arrary[i]; //更新最大值數(shù)組
  }
  if (maxlist[i] > max)
  {
   max = maxlist[i]; //用當(dāng)前值更新最大值
   end = i; //設(shè)置終點索引
  }
 }
 //下面幾句是尋找起始點
 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;
}