Subarray Sum Maximum

思路

对于subarray sum/product求max/min的问题，我们都要考虑使用local/global dp来做。

既然是动态规划，我们就要明确状态定义和状态转移方程。global[i]表示，在前i+1个数里所能找到的maximum sum；local[i]表示，包含(i+1)th个数的subarray里面的最大值。

转移方程则是: local[i] = Math.max(local[i-1] + cur, cur); global[i] = Math.max(global[i-1], local[i]);

步骤

因为是动态规划解法，所以我们要follow动态规划四要素：

• 状态定义：如上所述
• 状态初始化：这里当前问题的状态只和前一个子问题有关，所以我们只需要初始化local[0] = global[0] = nums[0]
• 状态转移方程：如上所述
• return 最终结果：return global[size-1]

题型变种

• 找一个subarray的maximum sum，直接应用以上思路就可以。
• 找一个 maximum sum的subarray的起止index，那么我们需要在每次start变化的时候keep track。
• 在circular array里面找一个subarray的maximum sum，那么思路就是做两次查找，一次查找maximum subarray sum，另一次查找minimum subarray sum，然后求补集。这两者中的最大值就是全局最大值。

• 找两个none-overlapping的subarray的maximum sum/diff，思路就是枚举分割线，然后在分割线左右两边求解再合并。

• 找k个subarray的maximum sum，核心就是二维DP。

  题目

• Lintcode 41. Maximum Subarray (1 subarray)
• Lintcode 42. Maximum Subarray II (2 subarrays)
• Lintcode 42. Maximum Subarray III (k subarrays)
• Lintcode 45. Maximum Subarray Difference (2 subarrays)
• Leetcode 53. Maximum Subarray