[Algo] 子数组最大累加和

1. 最大子数组和i

// 1. 最大子数组和i
// https://leetcode.cn/problems/maximum-subarray/description/
int maxSubArray(vector<int>& nums) {
    vector<int> dp(nums.size()); // dp[i] - 以i位置作为结尾的最大子数组和
    dp[0] = nums[0];
    for (int i = 1; i < dp.size(); i++) dp[i] = max(nums[i], nums[i] + dp[i - 1]);
    int ans = INT32_MIN;
    for (int i = 0; i < dp.size(); i++) ans = max(ans, dp[i]);
    return ans;
}

2. 最大子数组和ii

// 2. 最大子数组和ii
// 返回如下三个信息:
// 1) 最大累加和子数组的开头left
// 2) 最大累加和子数组的结尾right
// 3) 最大累加和子数组的累加和sum
// 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
vector<int> maxSubArr(vector<int>& nums)
{
    int left, right, sum = INT32_MIN;
    for (int i = 0, l = 0, r = 0, pre = INT32_MIN; i < nums.size(); i++)
    {
        if (pre <= 0) { l = i; r = i; pre = nums[i]; }
        else { r++; pre += nums[i]; }
        if (pre > sum) { left = l; right = r; sum = pre; }
    }
    vector<int> ans = {left, right, sum};
    return ans;
}

3. 数组中不能选相邻元素的最大累加和

// 3. 数组中不能选相邻元素的最大累加和
// https://leetcode.cn/problems/house-robber/description/
int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    vector<int> dp(nums.size()); // dp[i] - nums[0...i]不能选相邻元素的最大累加和
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < nums.size(); i++)
    dp[i] = max(dp[i - 1], max(nums[i], dp[i - 2] + nums[i]));
    return dp[nums.size() - 1];
}

4. 环形数组的子数组最大累加和

// 4. 环形数组的子数组最大累加和
// https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
int maxSubarraySumCircular(vector<int>& nums) {
    int maxSum = INT32_MIN, maxPre = INT32_MIN, minSum = INT32_MAX, minPre = INT32_MAX, all = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        all += nums[i];
        if (maxPre < 0) maxPre = nums[i];
        else maxPre += nums[i];
        maxSum = max(maxSum, maxPre);
        if (minPre > 0) minPre = nums[i];
        else minPre += nums[i];
        minSum = min(minSum, minPre);
    }
    // maxSum: 普通子数组最大累加和, all - minSum: 环状子数组最大累加和
    return minSum == all ? maxSum : max(maxSum, all - minSum); // !!!
}

5. 打家劫舍 IV

// 5. 打家劫舍 IV
// https://leetcode.cn/problems/house-robber-iv/
int mostRob1(vector<int>& nums, int capability)
{
    // 动态规划
    int n = nums.size();
    if (n == 1) return nums[0] <= capability ? 1 : 0;
    vector<int> dp(n);
    dp[0] = nums[0] <= capability ? 1 : 0;
    dp[1] = (nums[0] <= capability || nums[1] <= capability) ? 1 : 0;
    for (int i = 2; i < n; i++)
    dp[i] = max(dp[i - 1], nums[i] <= capability ? 1 + dp[i - 2] : 0);
    return dp[n - 1];
}
int mostRob2(vector<int>& nums, int capability)
{
    // 贪心策略
    int ans = 0;
    for (int i = 0; i < nums.size();)
    {
        if (nums[i] <= capability) { ans++; i += 2; }
        else i++;
    }
    return ans;
}
int minCapability(vector<int>& nums, int k) {
    int n = nums.size(), minVal = INT32_MAX, maxVal = INT32_MIN;
    for (int i = 0; i < n; i++) { minVal = min(minVal, nums[i]); maxVal = max(maxVal, nums[i]); }
    int l = minVal, r = maxVal, mid, ans;
    while (l <= r)
    {
        mid = l + (r - l) / 2;
        if (mostRob2(nums, mid) >= k) { ans = mid; r = mid - 1; }
        else l = mid + 1;
    }
    return ans;
}

6. 子矩阵最大累加和

// 6. 子矩阵最大累加和
// https://leetcode.cn/problems/max-submatrix-lcci/
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    vector<int> cur(m);
    int maxSum = INT32_MIN, r1, c1, r2, c2;
    for (int i = 0; i < n; i++)
    {
        fill(cur.begin(), cur.end(), 0);
        for (int j = i; j < n; j++)
        {
            for (int k = 0; k < m; k++) cur[k] += matrix[j][k];
            vector<int> ans = maxSubArr(cur);
            int left = ans[0], right = ans[1], sum = ans[2];
            if (sum > maxSum) { maxSum = sum; r1 = i; c1 = left; r2 = j; c2 = right; }
        }
    }
    vector<int> result = {r1, c1, r2, c2};
    return result;
}