325. Maximum Size Subarray Sum Equals k

When I saw this problem, my first impression is that it is similar to maximum subarray sum which can be solved by Kadane's algorithm. But this problem requires sum to be k. So, if we have sum[i] to be the sum from [0, i], the problem becomes to find all pairs of sum[i] == k or sum[i]-sum[j] == k. For sum[i] == k, the len is i+1, for sum[i]-sum[j] == k, the length is j - i. If we can save all sums before i in a hash table whose (key, value) pair is (sum, index), to get j which sum[i]-sum[j] == k, we only need to look up the hash table to see if sum[i]-k exists in it.

Note, since we scan from 0 to n, if sum[i] == k, the max length so far must be i+1. Also to avoid duplicates, we only save (sum, i) when this pair isn't existing in hash table. Why we don't have to save the pair (sum, j) later? Because we want to get the maximum size, the first pair guarantees it.

1:  class Solution {  
2:  public:  
3:    int maxSubArrayLen(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      int sum = 0, maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        sum += nums[i];  
8:        if (k == sum) maxLen = i+1;  
9:        else if (mp.find(sum-k) != mp.end()) maxLen = max(maxLen, i-mp[sum-k]);  
10:        if (mp.find(sum) == mp.end()) mp[sum] = i;  
11:      }  
12:      return maxLen;  
13:    }  
14:  };  

121. Best Time to Buy and Sell Stock

This is actually a maximum subarray sum problem which can be solved by Kadane’s Algorithm.
Here is a very good video explaining this algorithm:
https://www.youtube.com/watch?v=86CQq3pKSUw

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int maxGlobal = 0;  
5:      int maxCurrent = 0;  
6:      for (int i = 1; i < prices.size(); i++) {  
7:        maxCurrent = max(prices[i]-prices[i-1], maxCurrent + prices[i]-prices[i-1]);  
8:        if (maxCurrent > maxGlobal) maxGlobal = maxCurrent;  
9:      }  
10:      return maxGlobal;  
11:    }  
12:  };  

363. Max Sum of Rectangle No Larger Than K

I don't have idea to solve this problem so I followed the top rated solution. First of all, the solution follows idea in the link (https://www.youtube.com/watch?v=yCQN096CwWM) to solve maximum sum rectangle submatrix in a matrix. And the problem modified it a little bit to get the closest sum to K instead of maximum sum.
Let's say we have four points, left, right, top and bottom. A submatrix can be determined by these four points. Note left and right point can be determined by columns and top and bottom point can be determined by rows. Once we fixed the left and right points and do the sum from left to right for each row, the original problem becomes finding the subarray that has closest sum to K. Therefore, we can have two loops for all combinations of left and right.
To solve the subarray problem, we follow the same idea to do the cumulative sum. For subarray (i, j], we can compute the subarray sum by cum[j]-cum[i]. For the requirement cum[j]-cum[i] <= k, for a new cum[j], all we need to do is to search the cum before such that cum[i] >= cum[j]-k. Now, the problem become find the right cum[i] before j. This can be done by binary search or by building binary search tree.
The solution uses set<int> which is a binary search tree. Also it is very important to insert a 0 in first place because for cum[0], the requirement cum[j]-cum[i] <= k isn't valid since there isn't i. However, we can think of cum[i] as 0 and that's why we need to insert 0 initially.

1:  class Solution {  
2:  public:  
3:    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {  
4:      int row = matrix.size();  
5:      if (row == 0) return 0;  
6:      int col = matrix[0].size();  
7:      int res = INT_MIN;  
8:      // left point  
9:      for (int l = 0; l < col; l++) {  
10:        vector<int> sum(row, 0);  
11:        // right point  
12:        for (int r = l; r < col; r++) {  
13:          // from top point to bottom point  
14:          for (int i = 0; i < row; i++) {  
15:            sum[i] += matrix[i][r];  
16:          }  
17:          // for cum[], we want find cum[j]-cum[i] <= k  
18:          // so the problem becomes finding cum[i] >= cum[j] - k  
19:          // we use binary search tree here for cum[]  
20:          set<int> cum;  
21:          cum.insert(0);  
22:          int cum_j = 0, best = INT_MIN;  
23:          for (int j = 0; j < sum.size(); j++) {  
24:            cum_j += sum[j];  
25:            // get cum[i] such that cum[i] >= cum[j]-k;  
26:            auto cum_i = cum.lower_bound(cum_j-k);  
27:            if (cum_i != cum.end()) best = max(best, cum_j-*cum_i);  
28:            cum.insert(cum_j);  
29:          }  
30:          res = max(res, best);  
31:        }  
32:      }  
33:      return res;  
34:    }  
35:  };