// 最大子段和.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

using namespace std;

int MaxSum_test(int v[], int l, int r)

{

 int k,sum = 0;

 if (l ==r)

 {

   return v[l] >= 0 ? v[l]:0;

 }

 else

 {

  int center = (l+ r) / 2;

  int  lsum = MaxSum_test(v, l, center);

  int rsum = MaxSum_test(v, center + 1, r);

  int s1 = 0;

  int lefts = 0;

  for (k = center; k >= l; k--)

  {

   lefts += v[k];

   if (lefts>s1)

    s1 = lefts;

  }

  int s2 = 0;

  int rights = 0;

  for (k = center + 1; k <= r; k++)

  {

   rights += v[k];

   if (rights>s2)

    s2 = rights;

  }

  sum = s1 + s2;

  if (sum<lsum)

   sum = lsum;

  if (sum<rsum)

   sum = rsum;

 }

 return sum;

}

int _tmain(int argc, _TCHAR* argv[])

{

 int arr[6] = { -20, 11, -4, 13, -5, -2 };

 cout <<"最大子段长度为："<< MaxSum_test(arr, 0, 5) << endl;

 return 0;

}