参加了CVTE的2017实习生招聘在线笔试，最后一道编程题，写出了思路，但是无奈时间不太够，没有把代码完全写出来，现趁着有时间把思路整理一下，把实现代码写出来，也是一个不错的总结，也让我对DP有了更好的理解。网上搜索，发现这道题是《编程之美》中的一道题，所以也得出一个结论，这本书也是找工作实习必刷的大菜。

题目描述

有N个元素的整型数组arr，有正有负，数组中连续一个或多个元素组成一个子数组，这个数组当然有很多子数组，求子数组之和的最大值及相应的子数组。
例如：输入[0，-2，3，5，-1，2]应返回7和[3,5,-1]，输入[-9，-2，-3，-5，-3]应返回-2，[-2];
要求设计一个o(n)的算法求解。

问题分析

如果是用基本方法，找出所有的子数组，然后求和，取最大值，时间复杂度必然超过o(n),由于有子问题具有重叠性，可以考虑用 动态规划 求解，下面我就一步步分析，先由子数组之和的最大值分析求解引出，然后在求解子数组的始末下标，得到子数组。

求解子数组之和的最大值

考虑用DP求解，从后往前分析，考虑 最后一个元素 arr[n-1]与最大子数组的关系，有下面三种情况(相应的3个子问题)：

arr[n-1]单独构成最大子数组
最大子数组以arr[n-1]结尾
最大子数组跟arr[n-1]没有关系，最大子数组在arr[0—n-2]之间，转换为考虑元素arr[n-2]

现假设：

以arr[n-1]为结尾的最大子数组和为End[n-1]
在[0—n-1]范围内最大的子数组和为All[n-1]

则有：

子问题1，对应arr[n-1]
子问题2，对应End[n-1],有关系End[n-1]= max{End[n-2]+arr[n-1], arr[n-1]};
子问题3，对应All[n-2]

则有: All[n-1] = max(arr[n-1], End[n-1], All[n-2]); n>1
从后往前考虑，初始化情况为：End[0]=All[0]=arr[0]; n=1；

则根据分析，有 状态转移方程：
All[i] = max{arr[i],End[i-1]+arr[i],All[i-1]}
给出代码：

基础代码

#define max(a,b) (a>b ? a : b)
int Maxsum_dp(int *arr, int size)
{
  int End[30] = {-INF};
  int All[30] = {-INF}；
  End[0] = All[0] = arr[0];//初始化
  for (int i = 1; i< size; i++)
  {
    End[i]= max(End[i-1]+arr[i],arr[i]);//此处的理解：只是将状态转移方程分成两部分，说明End[n-2]为一个负数时，返回arr[n-1]
    All[i]= max(End[i],All[i-1]);
  }
 return All[size-1];
}

从上述代码中分析，只要我们从头遍历数组，累加求和，如果累加求和小于0（对应End[i-1]）,则从当前元素重新开始计数，
否则就一直累加，求其中的最大值即可。

扩展版代码

int Maxsum_ultimate(int * arr, int size)
{
    int maxSum = -INF;
    int sum = 0;
    for(int i = 0; i < size; ++i)
    {
        if(sum < 0)
        {
            sum = arr[i];
        }else
        {
            sum += arr[i];
        }
        if(sum > maxSum)
        {
            maxSum = sum;
        }
    }
    return maxSum;
}

求解子数组之和最大值对应的子数组，即返回最大子数组的始末位置

分析：从扩展版代码中，可以知道，每当当前子数组的和（sum）小于0时，便是新一轮子数组的开始；每当更新最大和（maxSum）时，便对应可能的结束下标，此时只要用本轮的起始和结束位置更新对应的最大子数组的始末位置即可，直到程序结束，最大子数组的始末位置即被记录下来。

void Maxsum_location(int * arr, int size, int & start, int & end)
{
    int maxSum = -INF;
    int sum = 0;
    int substart = start = 0;  /* substart记录每次当前起始位置 */
    for(int i = 0; i < size; ++i)
    {
        if(sum < 0)
        {
            sum = arr[i];
            substart = i;     /* 记录当前的起始位置 */
        }else
        {
            sum += arr[i];
        }
        if(sum > maxSum)
        {
            maxSum = sum;
            start = substart; /* 记录并更新最大子数组起始位置 */
            end = i;
        }
    }
}

参考博文

最大子数组和
 三种算法求解一个数组的子数组最大和