Range|Range Sum系列 RangeSum系列

https://leetcode.com/problems/maximum-subarray/
https://leetcode.com/problems/maximum-product-subarray/
https://leetcode.com/problems/range-sum-query-immutable/
https://leetcode.com/problems/range-sum-query-2d-immutable/
https://leetcode.com/problems/range-sum-query-mutable/ (树状数组，线段树，见别文)
https://leetcode.com/problems/range-sum-query-2d-mutable/ (树状数组，线段树，见别文)
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/（哈希表）
https://leetcode.com/problems/minimum-size-subarray-sum/（two pointers，binary search）
【Range|Range Sum系列】https://leetcode.com/problems/maximum-subarray/

dp[0] = nums[0]; dp[i] = dp[i-1] > 0 ? dp[i-1] : 0 + nums[i];

https://leetcode.com/problems/maximum-product-subarray/

int dpmin = nums[0]; int dpmax = nums[0]; if(nums[i] < 0) swap(dpmin, dpmax); dpmax = max(nums[i],dpmax*nums[i]); dpmin = min(nums[i],dpmin*nums[i]);

https://leetcode.com/problems/range-sum-query-immutable/

class NumArray { vector sums; public: NumArray(vector &nums) { int n = nums.size(); sums.resize(n+1,0); for(int i = 1; i <= n; i++) sums[i] = sums[i-1] + nums[i-1]; }int sumRange(int i, int j) { return sums[j+1] - sums[i]; } };

https://leetcode.com/problems/range-sum-query-2d-immutable/

class NumMatrix { vector > sums; public: NumMatrix(vector> &matrix) { int m = matrix.size(); if(m == 0) return; int n = matrix[0].size(); sums.resize(m+1,vector(n+1,0)); //init for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + matrix[i-1][j-1]; } } }int sumRegion(int row1, int col1, int row2, int col2) { if(row1 > row2 || col1 > col2) return 0; int area = sums[row2+1][col2+1]; area -= sums[row1][col2+1]; area -= sums[row2+1][col1]; area += sums[row1][col1]; return area; } };

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
要求=k

class Solution { public: int maxSubArrayLen(vector& nums, int k) { unordered_map sums; int sum = 0; int m = 0; sums[0] = -1; for(int i = 0; i < nums.size(); i ++) { sum += nums[i]; if(sums.find(sum - k) != sums.end()) { m = max(m, i - sums[sum - k]); } if(sums.find(sum) == sums.end()) { sums[sum] = i; } } return m; } };

https://leetcode.com/problems/minimum-size-subarray-sum/
要求>=k，two pointers方法如下。
binary search方法略，大概是存储sums，再去找sum-sums[i]>=k的临界位置吧。

class Solution { public: int minSubArrayLen(int s, vector& nums) { int minLen = INT_MAX; int left = 0; int sum = 0; for(int right = 0; right < nums.size(); ++right) { sum += nums[right]; while(sum >= s) { minLen = min(minLen, right - left + 1); sum -= nums[left++]; } } return (minLen == INT_MAX) ? 0 : minLen; } };