LeetCode 75 - 1493. Longest Subarray of 1's After Deleting One Element

Description

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:

1
2
3
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:

1
2
3
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:

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

Constraints:

1 <= nums.length <= 105
nums[i] is either 0 or 1.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n), suf(n);
        pre[0] = nums[0];
        suf[n - 1] = nums[n - 1];

        for (int i = 1; i < n; ++i) {
            pre[i] = nums[i] ? pre[i - 1] + 1 : 0;
        }

        for (int i = n - 2; i >= 0; --i) {
            suf[i] = nums[i] ? suf[i + 1] + 1 : 0;
        }

        int sum{};
        for (int i = 0; i < n; ++i) {
            int preSum = i == 0 ? 0 : pre[i - 1];
            int sufSum = i == n - 1 ? 0 : suf[i + 1];
            sum = std::max(sum, preSum + sufSum);
        }
        return sum;
    }
};