解题思路：动态规划问题。给出数组array[ ]，假定 f(i)代表array数组中以array[ i ]元素结尾的子数组的最大和，则可推得动态转换方程为
f(i) = f(i - 1) > 0 ? f(i - 1) + array[ i ] : array[ i ]
穷举所有的f( i )，返回最大的一个。
实现代码：
package com.lxqn.jiapeng.leetcode;
/**
* leetcode 53
* Created by jiapeng on 2017/11/16.
*/
public class MaxSumSubArray {
public static void main(String[] args) {
int[] array = {-1,2,3,-6,2,3,-1,2};
findMaxSumSubArray(array);
}
public static void findMaxSumSubArray(int[] array){
// f(i) = f(i - 1) > 0 ? f(i - 1) + array[ i ] : array[ i ]
int length = array.length;
//动态规划的关键，动态方程式的定义确认
//dp[i]表示以array[i]结尾的，最大子数组和
int[] dp = new int[length];
dp[0] = array[0];
int maxSum = array[0];
for (int i= 1;i<length; i++){
dp[i] = dp[i-1] > 0 ? dp[i-1] + array[i] : array[i];
maxSum = Math.max(dp[i],maxSum);
}
System.out.println("maxSum="+maxSum+ " ");
//
}
}
