问题描述

给定由n个整数组成的序列(a1,a2, …,an)，求该序列形如
$$S_n=\sum_{i=0}^{n}a_i$$
的子段和的最大值

题目分析

首先看暴力解法怎么做：
假设我们有函数 sum(int a[],int begin,int end) 计算a数组里面，begin到end间所有元素的总和

int getMaxSum(int n,int data[]){
  int maxSum = 0;
  for( int i = 1 ; i < n ; i ++ ){
    for (int j = i ; j < n ; j ++ ) {
      int sumTemp = sum( data, i , j);
      maxSum = (sumTemp < maxSum)?maxSum:sumTemp;
    }
  }
  return maxSum;
}

我们会发现 sum( data, i , j) 会被执行好多次，优化的策略肯定是优化这个循环的过程。
看到sum(data,i,j)有一个这样的规律 sum(data,i,j) == sum(data,i,j-1) + data[j]
那么，sum(data, 0 , 0 ) == data[0]
如果有一个数组array存放每一步的和，我们就可以得出递推关系
array[0] = data[0]
array[i] = array[i-1] + data[i] ( i >= 1 )
因为我们需要求最大字段和
那么有：
array[i-1] + data[i] > array[i]中，array[i-1] <= 0 时，会令字段和保持不变或缩小
因此我们在累计时，需要忽略array[i-1]<0的情况

… 说得有点乱 …. 直接上代码吧

代码实现

#include<iostream>

using namespace std;

int maxArray[20];

int max(int n1,int n2){
  return (n1>n2)?n1:n2;
}

int getMaxSum(int n,int data[]){
  maxArray[0] = data[0];
  int maxSum = maxArray[0];
  for( int i = 1 ; i < n ; i ++ ){
    if(maxArray[i-1]>0){
      maxArray[i] = maxArray[i-1]+data[i];
    }else{
      maxArray[i] = data[i];
    }
  }
  for(int i = 0 ; i < n ; i ++ ){
    maxSum = max(maxArray[i],maxSum);
  }
  return maxSum;
}

int main(){
  int data[] = {-2,11,-3,13,-5,-2};
  int n = 6;
  cout<<getMaxSum(n,data)<<endl;
  return 0;
}