连续子数组之和最大

#include

static int Start = 0;

static int End = 0;

/*

该算法是穷举法，时间复杂度为O(n^3).第一二层循环迭代了所有肯能的连续子序列，第三层循环里tempSum += a[n]就是计算各子序列的和。然后tempSum再与max作比较，求出终结果。Start、End分别记录了子序列的起始和终止位置（数组下标从0开始算）。

*/

int fun(int a[], int n) //n是数组元素的个数

{

int i,j,k,tempSum;

int max = 0;

for (i = 0; i < n; i++)

for (j = i; j < n; j++)

{

tempSum = 0;

for (k = i; k <= j; k++)

{

tempSum += a[k];

}

if (tempSum > max)

{

max = tempSum;

Start = i;

End = j;

}

}

return max;

}

/*

该算法是基于上一个算法的改进，算法的时间复杂度为O(n^2).在这算法中去掉了上面那个

算法的第二层循环，原因在于，从a[i]加到a[j]的tempSum等于a[i]加到a[j-1]的tempSum

,所以就没必要在来一层循环重新算tempSum了。

*/

int fun2(int a[], int n)

{

int i,j,tempSum;

int max = 0;

for (i = 0; i < n; i++)

{

tempSum = 0;

for (j = i; j <= n; j++)

{

tempSum += a[j];

if (tempSum > max)

{

max = tempSum;

//Start = i;

//End = j;

}

}

}

return max;

}

/*

该算法是线性算法。我们在计算最大连续子窜的时候会发现一个规律：a[i]至a[j]之和sum

若小于零，那么a[j]后面的项再与sum相加的和一定小于没有加上sum之前的和大。根据这个我们可以设计出如下算法。

*/

int fun3(int a[], int n)

{

int i,j;

int max = 0;

int tempSum = 0;

for (i = 0,j = 0; j < n; j++)

{

tempSum += a[j];

if (tempSum > max)

{

max = tempSum;

//Start = i;

//End = j;

}

else if (tempSum < 0) //若tempSum小于0，下次直接从第j+1项开始加

{

i = j + 1;

tempSum = 0;

}

}

return max;

}

#include
using namespace std;

typedef struct Result
{
 int sum;
 int begin;
 int end;
}Result;

Result getMaxSubArraySum(int*array, int len)
{
 Result result;
 result.sum = result.begin = result.end = 0;
 int tmpSum = 0;
 int tmpBegin = 0;
 for(int i=0; i  {
  if(tmpSum + array[i] > 0)
  {
   tmpSum += array[i];
   if(result.sum < tmpSum)
   {
    result.end = i;
    result.begin = tmpBegin;
    result.sum = tmpSum;
   }
  }
  else
  {
   tmpSum = 0;
   tmpBegin = i+1;
  }
 }
 return result;
}

int main()
{
 int arr[] = {2,-3,10,-4,3,1,-2,5,-2,11};
 int len = sizeof(arr)/sizeof(int);
 Result re = getMaxSubArraySum(arr, len);
 cout<  cin >> arr[0];
     return 0;
}