Leetcode 1288 Solution

This article provides solution to leetcode question 1288 (maximum-subarray-sum-with-one-deletion)
Categories:
Tags:
Access this page by simply typing in "lcs 1288" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion

Solution

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        dp1 = [arr[0]] * n
        dp2 = [arr[0]] * n

        for i in range(1, n):
            dp1[i] = max(dp1[i - 1] + arr[i], arr[i])
            dp2[i] = max(dp2[i - 1] + arr[i], arr[i])

            if i >= 2:
                dp2[i] = max(dp2[i], dp1[i - 2] + arr[i])

        return max(dp2)