简单的动态规划说明：
题目说明：输入一个整型数组 ， 数组中的一个或连续多个整数组成一个子数组 。 求所有子数组的和的最大值 。
要求时间复杂度为O(n) 。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大 ， 为 6 。
来源：力扣（LeetCode）
链接：
著作权归领扣网络所有 。 商业转载请联系官方授权 ， 非商业转载请注明出处 。
假设我们设f(n)为到第n个数组元素时 ， 可能存在的子数组的最大值 。 nums为提供的原数组 。
我们通过动态规划的方程可以简单罗列出方程的思路：
【动态规划从零开始（1）-剑指Offer 42】f(n) = max{f(n-1)+nums(n),nums(n)}；
简而言之 ， 要么是第[n]元素和之前的值加在一起是最大的 ， 要么[n]元素本身的大小就超过了f(n-1)+nums[n] 。
所以我们需要一个对象dp[n]来记录【当前路径的最大值】 ， 一个对象max来存储【已经走完的路径的最大值】 。 为什么还要max呢？因为走完整个数组后 ， 最大的一段数组可能是在前面、中间或后面 ， dp完成后的值未必是最大值 。
如[9,-1,-2,-3] ， dp[3]=3 ， 但max=9 。 所以dp[n]的目的是遍历整个数组 ， 同时利用max进行记录 。
代码：Java
执行用时：1 ms, 在所有 Java 提交中击败了99.42%的用户
class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int max = dp[0];for (int i =1;i对于大部分Leetcode-Easy难度的动态规划题 ， 本质上的解法就是
f(n)={selector}(f(n-1),n) ， 其中{selector}指Math.max,Math.min等数学选择方法 。