Range Sum系列

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）

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<int> sums;
public:
    NumArray(vector<int> &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<vector<int> > sums;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        if(m == 0) return;
        int n = matrix[0].size();
        sums.resize(m+1,vector<int>(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<int>& nums, int k) {
        unordered_map<int,int> 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<int>& 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;
    }
};