发表于 2024.07.05

• 最大和子数组的变种题目，新增了一个允许删除一个元素的条件。对于最大和子数组，其中以第i个元素结尾的子数组最大和为dp[i] = max(dp[i-1] + nums[i], nums[i])。对于本题，我们可以使用二维n * 2的dp数组，其中dp[i][0]和dp[i][1]分别表示以第i个元素结尾的非空子数组，不删除元素和删除一个元素的情况下的最大和。对于不删除元素的情况，dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])；对于删除一个元素的情况，dp[i][1] = max(dp[i - 1][0], dp2[i-1] + nums[i])(即要么是删除本元素，要么就是不删除本元素，删除的操作在前面的元素)。最终结果即为上述循环中最大的数组值，注意不能取dp[0][1]，因为题目要求子数组非空的。(2024-07-21更新实际上，dp[0][1]是不符合上述的非空子数组要求的，只不过这里为了方便计算，将dp[0][1]设置为初始值0，但不计入结果)

  class Solution:
      def maximumSum(self, arr: List[int]) -> int:
          # dp[i][0]: 以第i个元素结尾的, 没有进行删除操作的子数组最大和
          # dp[i][1]: 以第i个元素结尾的, 进行了一次删除操作的子数组最大和
          dp = [[0, 0] for _ in range(len(arr))]
          dp[0][0] = arr[0]
          # 注意这里的ans初始值不能考虑dp[0][1], 因为题目要求子数组是非空的
          ans = dp[0][0]
  
          for i in range(1, len(arr)):
              dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i])
              dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i])
              ans = max(ans, dp[i][0], dp[i][1])
          return ans

  C++的做法：

  class Solution {
  public:
      int maximumSum(vector<int>& arr) {
          vector<vector<int>> dp(arr.size(), vector<int>(2, 0));
          dp[0][1] = 0; dp[0][0] = arr[0];
          int ans = arr[0];
          for (int i = 1; i < arr.size(); ++i) {
              // update dp[i][0]
              dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
              // update dp[i][1]
              dp[i][1] = max(
                  dp[i - 1][0],
                  dp[i - 1][1] + arr[i]
              );
              ans = max(ans, max(dp[i][0], dp[i][1]));
          }
          return ans;
      }
  };

  使用滚动dp压缩空间的做法，即只使用两个变量dp0和dp1来表示dp[i][0]和dp[i][1]，可以将空间复杂度降低为O(1)。

  class Solution:
      def maximumSum(self, arr: List[int]) -> int:
          # dp[i][0]: 以第i个元素结尾的, 没有进行删除操作的子数组最大和
          # dp[i][1]: 以第i个元素结尾的, 进行了一次删除操作的子数组最大和
          dp0, dp1 = arr[0], 0
          # 注意这里的ans初始值不能考虑dp[0][1], 因为题目要求子数组是非空的
          ans = dp0
  
          for i in range(1, len(arr)):
              dp0, dp1 = max(dp0 + arr[i], arr[i]), max(dp0, dp1 + arr[i])
              ans = max(ans, dp0, dp1)
          return ans

  C++的滚动dp做法：

  class Solution {
  public:
      int maximumSum(vector<int>& arr) {
          int dp1 = 0, dp0 = arr[0];
          int ans = arr[0];
          for (int i = 1; i < arr.size(); ++i) {
              // update dp[i][0]
              int new_dp0 = max(dp0 + arr[i], arr[i]);
              // update dp[i][1]
              int new_dp1 = max(
                  dp0,
                  dp1 + arr[i]
              );
              dp0 = new_dp0; dp1 = new_dp1;
              ans = max(ans, max(dp0, dp1));
          }
          return ans;
      }
  };

• LC 题目链接