1186. Maximum Subarray Sum with One Deletion

題目網址：https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/

題意：給一整數 array, 返回其 non-empty subarray（連續元素）在執行最多一次的刪除操作後, 所能得到的最大元素總和。

注意：刪除一個元素後的 subarray 不能為空。

Solution 1：

想法：利用 DP

1. 定義狀態：

首先, 會在 arr 前先加上一個 0, 代表什麼元素都沒有的狀態

noDel[i]：arr[1:i] 中, 沒有任何刪除操作的最大 subarray 和

oneDel[i]：arr[1:i] 中, 有一次刪除操作的最大 subarray 和

2. 得到狀態轉移方程：

noDel[i]：由於沒有刪除操作, 故 arr[i] 一定在 subarry 中, 因此有兩種可能

以 arr[i] 為結尾, 所有往前延伸之 subarray 中最大的（subarray.size() > 1）
➔ 遞迴調用 noDel[i - 1] + arr[i]

只有 arr[i]（前面 arr[0:(i-1)] 皆為負數, 加了只會更小, 不如不加）

➔ noDel[i] = max(noDel[i - 1] + arr[i], arr[i])

oneDel[i]：有兩種可能

arr[1:i] 沒任何刪除操作, 刪除的是 arr[i] ➔ noDel[i - 1]

arr[1:i] 已經有一次刪除操作, 所以 arr[i] 不刪除
➔ oneDel[i - 1] + arr[i]

➔ oneDel[i] = max(oneDel[i - 1] + arr[i], noDel[i - 1])

3. 初始化：

noDel[0]、oneDel[0]：當沒有元素時, 最大元素總和為 0

noDel[1]：只有一個元素 arr[1] 時, 且沒有任何刪除操作
➔ noDel[1] = arr[1]

oneDel[1]：只有一個元素 arr[1] 時, 且有一次刪除操作
**➔ oneDel[1] = 0**（arr[1] 被刪除）

res：照理來說, res 為上述兩者中取較大者, 也就是 res = max(0, arr[1])（arr[1] 有可能為負數）。但是, 題目有規定刪除一個元素後 subarray 不能為空, 所以當只有一個元素時, 是不能有任何刪除操作的, 所以 res 只能為 noDel[1], 也就是 arr[1]➔ res = arr[1]

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        const int n = arr.size();
        vector<int> noDel(n + 1, 0);
        vector<int> oneDel(n + 1, 0);

        arr.emplace(arr.begin(), 0);
        noDel[1] = arr[1], oneDel[1] = 0;
        int res = arr[1];

        for (int i = 2; i <= n; ++i) {
            noDel[i] = max(noDel[i - 1] + arr[i], arr[i]);
            oneDel[i] = max(oneDel[i - 1] + arr[i], noDel[i - 1]);
            res = max({res, noDel[i], oneDel[i]});
        }

        return res;
    }
};

time：$O(n)$ ➔ for loop
space：$O(n)$ ➔ noDel, oneDel

Solution 2：

想法：改進 Solution 1, 由於 noDel[i], oneDel[i] 只會用到第 i - 1 次的狀態, 因此只需儲存上一次的狀態即可, 根本不需要開到 $O(n)$ space。由於 oneDel[i] 會用到 noDel[i - 1], 所以要先更新 oneDel, 再更新 noDel, 這樣才不會使 oneDel 拿到新的 noDel

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        const int n = arr.size();

        arr.emplace(arr.begin(), 0);
        int noDel = arr[1], oneDel = 0, res = arr[1];

        for (int i = 2; i <= n; ++i) {
            oneDel = max(oneDel + arr[i], noDel);
            noDel = max(noDel + arr[i], arr[i]);
            res = max({res, noDel, oneDel});
        }

        return res;
    }
};

time：$O(n)$ ➔ for loop
space：$O(1)$ ➔ 只需常數空間