leetcode 53题

解题思路：动态规划问题。给出数组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+ " ");
//
    }

}