[数据结构与算法]最大子数组问题（动态规划）

最大子数组问题可以通过动态规划将时间复杂度做到O(N），也是之前的算法导论4.1-5问题

动态规划问题
上文的分治思想，实际上是根据问题性质将其分解为小规模问题，之后逐步求解小问题得出结果，再利用这些结果得出原问题的解。
动态规划实际上也是这种思想，当问题具备重叠子问题，最优子结构的性质时，往往可通过此法得出答案。

对于最大子数组问题，采用dp数组解决
定义：dp[i]
i 为数组索引，是为“状态”，dp[i]为以索引i为终点的数组的前i+1个值的最大子数组和

考虑dp[i] 与 dp[i-1]的关系，是否可以通过dp[i-1]得到dp[i]呢？通过分析可以发现 dp[i] = Max{A[i] , dp[i-1] + A[i] }，根据该式，即完成了状态i-1到状态i的转移，是为“状态转移方程”。

根据以上得出程序：

// A code block
lass Solution {
    public int maxSubArray(int[] nums) {

       int len = nums.length;
       int[] dp = new int[len];  
       dp[0] = nums[0];
       int max = nums[0];
       for(int i = 1;i<len;i++){
          dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
           max = Math.max(max,dp[i]);
       }
       return max;
    }
}

考虑到只有dp[i] 和 dp[i-1]互相转移，进行路径压缩，使额外空间复杂度降为O(1)

// A code block
class Solution {
    public int maxSubArray(int[] nums) {
       int len = nums.length;
       int cur = nums[0];
       int ant = nums[0];
       for(int i = 1;i<len;i++){
          cur = Math.max(nums[i],cur+nums[i]);
          ant = Math.max(cur,ant);
       }
       return ant;
    }
}