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:
- 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]
).- 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).
- 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之和