# [LeetCode 363. Max Sum of Rectangle No Larger Than K](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3801/)
### Daily challenge Jul 3, 2021 (HARD)

>Given an **`m x n`** matrix **`matrix`** and an integer **`k`**, return the max sum of a rectangle in the matrix such that its sum is no larger than k.
>
>It is **guaranteed** that there will be a rectangle with a sum no larger than k.


:::info
**Example 1:**
**Input:** matrix = [[1,0,1],[0,-2,3]], k = 2
**Output:** 2
**Explanation:** Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
:::

:::info
**Example 2:**
**Input:** matrix = [[2,2,-1]], k = 3
**Output:** 3
:::

:::warning
**Constraints:**
* m == matrix.length
* n == matrix[i].length
* 1 <= m, n <= 100
* -100 <= matrix[i][j] <= 100
* -105 <= k <= 105
:::

---

### Approach 1 : Kadane Algorithm :book:
**`1064 ms ( 62.09% )`** **`O( min(m,n)^2 * max(m,n) * log(max(m,n)))`**
:::danger
**Kadane Algorithm** is a kind of DP approach and it can solve *`Maximum Sum Rectangular Submatrix in Matrix`*.
:movie_camera: [Easily Understanding Video](https://www.youtube.com/watch?v=yCQN096CwWM) :movie_camera:
:::

#### **Kadane Algorithm**
>1. 與 Sliding Window 相似，使用兩個 pointer ( left & right )，分別表示開始、結束位置，並將 **`每列的`** 計算結果存入 `SUM`。
>2. 從 `SUM` 中計算最大的總和。
>e.g. SUM = {2, 0, 2, -3}, maxSum = 2 + 0 + 2 = 4。
>>如何尋找 ?
>>* 將 `SUM` 從頭開始進行累加，並記錄當前總和 **`current = max(0, current)`** 以及最大值 **`MAX = max(current, MAX)`**。
>>* 若陣列內皆為 `負數` 則需要特別判斷 ---> 回傳陣列中的`最大值`即可。
>```cpp=
>class Kadanes{
> public static int GetMax(int[] SUM){
> // 無考慮皆為負數的狀況 //
> int current = 0;
> int MAX = SUM[0];
> for (int i = 0; i < SUM.size(); i++){
> current += SUM[i];
> current = max(0, current);
> MAX = max(current, MAX);
> }
>
> return MAX;
> }
>};
>```

#### 但是題目要求 No Larger Than K。
>需將 **Kadane Algorithm** 方法改進。
>* 紀錄所有的 `current` 存入 `set` 當中 ( 不使用 `max` 更改 `current` )。
>* 因為要找到 **`小於等於 K`** 的值，使用 **`set.lower_bound(current_sum - k)`** 找出是否有符合的答案。
>:::danger
>Why we use **`lower_bound(current_sum - k)`** ?
>
>:::spoiler
>| index | SUM | set |
>|:---:|:---:|:---:|
>| [0] | 3 | 3 |
>| [1] | 7 | 10 |
>| [2] | 8 | **current** |
>
>Assume **K = 16**。
>當 `i = 2` 時，`current = 10 + 8 = 18`雖然是最大值，但超過要求的 K = 16。
>根據公式 :
>$$
>set(i) - set(j) \le K
>$$
>其中 `i` 為當前位置，若能找到一個 `j` 使答案最接近 `K`，該值就是所求的答案。
>
>將 `K`, `set(j)` 移項後，可以推測出如果使用 **`lower_bound(current - k)`** 尋找 **`第一個大於等於 current - k`** 的 `set(j)`，就非常可能是我們想要的答案。
>* **`set(j) >= current`** ---> **`current - set(j) <= 0`**
>* **`set(j) < current`** ---> **`current - set(j) > 0`** 有可能是答案 :100:
>
>以上表格為例 :
>>**`i = 2, current = 18`** -> **`lower_bound(current - K) = 3`**。
>>**`ans = max(ans, current - 3) = 15。`**
>>可以推斷出當 `Rectangle` 是由 `[1]、[2]` 組成時，會有最大的答案。
>:::
>
>
>
>
>```cpp=20
>// find ans
>set<int > record;
>record.insert(0);
>int current_sum = 0
>
>for(int sum : kadane){
> current_sum += sum;
> auto it = record.lower_bound(current_sum - k);
> if(it != record.end()) ans = max(ans, current_sum - *it);
> record.insert(current_sum);
>}
>```
>:::success
>```cpp=22
>record.insert(0);
>```
>先加入 `0` 以避免 `第一項` 即為答案。
>:::

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if(matrix.empty())    return 0;

        int row = matrix.size();
        int col = matrix[0].size();
        int ans = INT_MIN;
        
        for(int left=0; left<col; left++){
            // reset vector
            vector<int > kadane(row, 0);
            
            for(int right=left; right<col; right++){
                // kadane algorithm -> count each col's sum
                for(int i=0; i<row; i++){
                    kadane[i] += matrix[i][right];
                }
                
                // find ans
                set<int > record;
                record.insert(0);
                int current_sum = 0
                
                for(int sum : kadane){
                    current_sum += sum;
                    auto it = record.lower_bound(current_sum - k);
                    if(it != record.end())  ans = max(ans, current_sum - *it);
                    record.insert(current_sum);
                }
            }
        }
        
        return ans;
    }
};