动态规划

子数组的最大累加和问题

这是一个典型的动态规划问题。

• 最优子结构

  在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。

• 重复子问题

  递归地寻找子问题的最优解时，子问题会重叠地出现在子问题里，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。

动态规划解题步骤：

1. 定义子问题
2. 写出子问题的递推关系
3. 确定DP数组的计算顺序

本题中的具体表现为：

    dp[i] 以i为结尾的最大和
    dp[i] = Math.max(dp[i], dp[i - 1] + arr[i]);
    dp[0] = arr[0];
    max = Math.max(dp[i]);

题解：

import java.util.*;

public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int len = arr.length;  
        int res = arr[0];      //最优解
        int dp = arr[0];       //自底而上解子问题 
        for(int i = 1; i < len; i++){
            dp = Math.max(arr[i], dp + arr[i]);
            res = Math.max(dp, res);
        }

        return res;
    }
}