本系列导航：剑指offer（第二版）java实现导航帖](http://www.jianshu.com/p/010410a4d419)
面试题42：连续子数组的最大和
题目要求：
输入一个整形数组，数组里有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为o(n)。
解题思路：
暴力求解，简单直接，但时间复杂度o(n^2)。
其实这种最值问题，很容易让人想到动态规划。对于数据data[],申请一个数组dp[]，定义dp[i]表示以data[i]为末尾元素的子数组和的最大值。dp的初始化及递推公式可表示为
dp[i] = data[i] i=0或dp[i-1]<=0
dp[i-1]+data[i] i!=0且dp[i-1]>0
由于dp[i]仅与dp的前一个状态有关，即在计算dp[i]时，dp[i-2],dp[i-3]......,dp[0]对于dp[i]没有影响，因此可以省去dp数组，用一个变量记录当前dp值，用另一个变量maxdp记录出现的最大的dp值。如此处理后，时间复杂度为o(n)，空间复杂度为o(1)。
package chapter5;
/**
* Created with IntelliJ IDEA.
* Author: ryder
* Date : 2017/8/1
* Time : 20:58
* Description:连续子数组的最大和
**/
public class P218_GreatestSumOfSubarrays {
//动态规划，递归公式：dp[i] = data[i] i=0或dp[i-1]<=0
// dp[i-1]+data[i] i!=0且dp[i-1]>0
//由于只需知道前一个情况的dp值，因此可省去dp数组，申请个变量记录即可
public static int findGreatestSumOfSumArrays(int[] data){
if(data==null || data.length==0)
return 0;
//dp[i]用于计算以data[i]为结尾元素的连续数组的最大和
//maxdp用于记录在上述过程中的最大的dp值
int dp = data[0],maxdp = dp;
for(int i=1;i<data.length;i++){
if(dp>0)
dp += data[i];
else
dp = data[i];
if(dp>maxdp)
maxdp = dp;
}
return maxdp;
}
public static void main(String[] args){
int[] data = {1,-2,3,10,-4,7,2,-5};
System.out.println(findGreatestSumOfSumArrays(data));
}
}
运行结果
18
