1493. Longest Subarray of 1's After Deleting One Element ⭐

Medium

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

• 1 <= nums.length <= 10^5

• nums[i] is either 0 or 1.

解題

參考花花的思路，使用dp來解

func longestSubarray(nums []int) int {
    l := len(nums)

    leftDp := make([]int, l)
    rightDp := make([]int, l)

    for i:=0; i<l; i++ {
        if i == 0 {
            leftDp[i] = nums[i]
        } else {
            leftDp[i] = (leftDp[i-1]+1)*nums[i]
        }
    }

    for i:=l-1; i>=0; i-- {
        if i==l-1 {
            rightDp[i] = nums[i]
        } else {
            rightDp[i] = (rightDp[i+1]+1)*nums[i]
        }
    }

    ans := 0
    for i:=0; i<l; i++ {
        if i==0 {
            ans = max(ans, rightDp[i+1])
        } else if i==l-1 {
            ans = max(ans, leftDp[i-1])
        } else {
            ans = max(ans, leftDp[i-1]+rightDp[i+1])
        }
    }

    return ans
}


func max(a, b int) int {
    if a > b { return a }
    return b
}