Subarray 问题

Subarray 问题常用思路

1. 从第i个到第j个 subarray 之和 转换成 sum(0,,j) - sum(0,,i)

使用典型题目：sum divide by k， sum equal to k，sum multiple of k

2. maximum subarray sum / product 

单一subarray问题，可以思考当1 pass到第i个的时候和已知包含（i-1）个关系，同时维持一个全局变量来记录所有已知的最优解

product稍微复杂一点，需要考虑0 reset 的问题

max_so_far is updated by taking the maximum value among:

1. Current number.
   • This value will be picked if the accumulated product has been really bad (even compared to the current number). This can happen when the current number has a preceding zero (e.g. [0,4]) or is preceded by a single negative number (e.g. [-3,5]).
2. Product of last max_so_far and current number.
   • This value will be picked if the accumulated product has been steadily increasing (all positive numbers).
3. Product of last min_so_far and current number.
   • This value will be picked if the current number is a negative number and the combo chain has been disrupted by a single negative number before (In a sense, this value is like an antidote to an already poisoned combo chain).

变种问题，比如两段/三段, 可以转化为用array来记录分别的最优解，然后最后再多一遍扫描来得到全局最优

left_array && right_array： 适用典型题目：maximum sum of 2 unoverlap array / 3 unoverlap array

可以转换成从左看 / 从右看 subarray之和