跳转至

3640. 三段式数组 II

题目描述

给你一个长度为 n 的整数数组 nums。

三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：

  • nums[l...p] 严格 递增，
  • nums[p...q] 严格 递减，
  • nums[q...r] 严格 递增。

请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。

 

示例 1：

输入：nums = [0,-2,-1,-3,0,2,-1]

输出：-4

解释：

选择 l = 1, p = 2, q = 3, r = 5：

  • nums[l...p] = nums[1...2] = [-2, -1] 严格递增 (-2 < -1)。
  • nums[p...q] = nums[2...3] = [-1, -3] 严格递减 (-1 > -3)。
  • nums[q...r] = nums[3...5] = [-3, 0, 2] 严格递增 (-3 < 0 < 2)。
  • 和 = (-2) + (-1) + (-3) + 0 + 2 = -4。

示例 2:

输入: nums = [1,4,2,7]

输出: 14

解释:

选择 l = 0, p = 1, q = 2, r = 3：

  • nums[l...p] = nums[0...1] = [1, 4] 严格递增 (1 < 4)。
  • nums[p...q] = nums[1...2] = [4, 2] 严格递减 (4 > 2)。
  • nums[q...r] = nums[2...3] = [2, 7] 严格递增 (2 < 7)。
  • 和 = 1 + 4 + 2 + 7 = 14。

 

提示:

  • 4 <= n = nums.length <= 105
  • -109 <= nums[i] <= 109
  • 保证至少存在一个三段式子数组。

解法

方法一：分组循环

我们可以遍历数组，寻找所有可能的极大三段式子数组，从而计算其和并更新最大值。

我们定义一个指针 \(i\)，初始时 \(i = 0\)，表示当前指向数组的第一个元素。我们将 \(i\) 向右移动，直到找到第一个不满足严格递增的元素，即 \(nums[i-1] \geq nums[i]\)。如果此时 \(i = l + 1\)，说明这一段只有一个元素，无法形成递增序列，因此继续下一个循环。

接下来，我们定义指针 \(p\)，表示当前递增段的结束位置。然后找出第二段严格递减的部分，如果这一段只有一个元素或者到达数组末尾，或者出现相等的元素，则继续下一个循环。

然后我们定义指针 \(q\)，表示当前递减段的结束位置。接着找出第三段严格递增的部分，这时，我们就找到了一个极大的三段式子数组。那么这个三段式子数组的最大和，由以下几个部分组成：

  • 下标范围 \([p-2,..,q+1]\) 的元素之和
  • 从 \(p-3\) 向左扩展的最大递增子数组之和，如果不存在则为 0
  • 从 \(q+2\) 向右扩展的最大递增子数组之和，如果不存在则为 0。

我们计算出这个三段式子数组的和后，更新答案。然后将指针 \(i\) 移动到 \(q\) 位置，这是因为第三段的递增部分可以作为下一次循环的第一段递增部分。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)，只使用了常数级别的额外空间。

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        ans = -inf
        while i < n:
            l = i
            i += 1
            while i < n and nums[i - 1] < nums[i]:
                i += 1
            if i == l + 1:
                continue

            p = i - 1
            s = nums[p - 1] + nums[p]
            while i < n and nums[i - 1] > nums[i]:
                s += nums[i]
                i += 1
            if i == p + 1 or i == n or nums[i - 1] == nums[i]:
                continue

            q = i - 1
            s += nums[i]
            i += 1
            mx = t = 0
            while i < n and nums[i - 1] < nums[i]:
                t += nums[i]
                i += 1
                mx = max(mx, t)
            s += mx

            mx = t = 0
            for j in range(p - 2, l - 1, -1):
                t += nums[j]
                mx = max(mx, t)
            s += mx

            ans = max(ans, s)
            i = q
        return ans

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public long maxSumTrionic(int[] nums) {
        int n = nums.length;
        int i = 0;
        long ans = Long.MIN_VALUE;
        while (i < n) {
            int l = i;
            i += 1;
            while (i < n && nums[i - 1] < nums[i]) {
                i += 1;
            }
            if (i == l + 1) {
                continue;
            }

            int p = i - 1;
            long s = nums[p - 1] + nums[p];
            while (i < n && nums[i - 1] > nums[i]) {
                s += nums[i];
                i += 1;
            }
            if (i == p + 1 || i == n || nums[i - 1] == nums[i]) {
                continue;
            }

            int q = i - 1;
            s += nums[i];
            i += 1;
            long mx = 0, t = 0;
            while (i < n && nums[i - 1] < nums[i]) {
                t += nums[i];
                i += 1;
                mx = Math.max(mx, t);
            }
            s += mx;

            mx = 0;
            t = 0;
            for (int j = p - 2; j >= l; j--) {
                t += nums[j];
                mx = Math.max(mx, t);
            }
            s += mx;

            ans = Math.max(ans, s);
            i = q;
        }
        return ans;
    }
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        long long ans = LLONG_MIN;
        while (i < n) {
            int l = i;
            i += 1;
            while (i < n && nums[i - 1] < nums[i]) {
                i += 1;
            }
            if (i == l + 1) {
                continue;
            }

            int p = i - 1;
            long long s = nums[p - 1] + nums[p];
            while (i < n && nums[i - 1] > nums[i]) {
                s += nums[i];
                i += 1;
            }
            if (i == p + 1 || i == n || nums[i - 1] == nums[i]) {
                continue;
            }

            int q = i - 1;
            s += nums[i];
            i += 1;
            long long mx = 0, t = 0;
            while (i < n && nums[i - 1] < nums[i]) {
                t += nums[i];
                i += 1;
                mx = max(mx, t);
            }
            s += mx;

            mx = 0, t = 0;
            for (int j = p - 2; j >= l; j--) {
                t += nums[j];
                mx = max(mx, t);
            }
            s += mx;

            ans = max(ans, s);
            i = q;
        }
        return ans;
    }
};

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func maxSumTrionic(nums []int) int64 {
    n := len(nums)
    i := 0
    ans := int64(math.MinInt64)
    for i < n {
        l := i
        for i++; i < n && nums[i-1] < nums[i]; {
            i++
        }
        if i == l+1 {
            continue
        }

        p := i - 1
        s := int64(nums[p-1]) + int64(nums[p])
        for i < n && nums[i-1] > nums[i] {
            s += int64(nums[i])
            i++
        }
        if i == p+1 || i == n || nums[i-1] == nums[i] {
            continue
        }

        q := i - 1
        s += int64(nums[i])
        i++
        var mx, t int64
        for i < n && nums[i-1] < nums[i] {
            t += int64(nums[i])
            i++
            mx = max(mx, t)
        }
        s += mx

        mx, t = 0, 0
        for j := p - 2; j >= l; j-- {
            t += int64(nums[j])
            mx = max(mx, t)
        }
        s += mx

        ans = max(ans, s)
        i = q
    }
    return ans
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function maxSumTrionic(nums: number[]): number {
    const n = nums.length;
    let i = 0;
    let ans = -Infinity;

    while (i < n) {
        const l = i;
        i += 1;

        while (i < n && nums[i - 1] < nums[i]) i += 1;
        if (i === l + 1) continue;

        const p = i - 1;
        let s = nums[p - 1] + nums[p];

        while (i < n && nums[i - 1] > nums[i]) {
            s += nums[i];
            i += 1;
        }
        if (i === p + 1 || i === n || nums[i - 1] === nums[i]) continue;

        const q = i - 1;
        s += nums[i];
        i += 1;

        let mx = 0,
            t = 0;
        while (i < n && nums[i - 1] < nums[i]) {
            t += nums[i];
            i += 1;
            mx = Math.max(mx, t);
        }
        s += mx;

        mx = 0;
        t = 0;
        for (let j = p - 2; j >= l; j--) {
            t += nums[j];
            mx = Math.max(mx, t);
        }
        s += mx;

        ans = Math.max(ans, s);
        i = q;
    }

    return ans;
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
impl Solution {
    pub fn max_sum_trionic(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut i = 0;
        let mut ans = i64::MIN;
        while i < n {
            let l = i;
            i += 1;
            while i < n && nums[i - 1] < nums[i] {
                i += 1;
            }
            if i == l + 1 {
                continue;
            }

            let p = i - 1;
            let mut s = nums[p - 1] as i64 + nums[p] as i64;
            while i < n && nums[i - 1] > nums[i] {
                s += nums[i] as i64;
                i += 1;
            }
            if i == p + 1 || i == n || nums[i - 1] == nums[i] {
                continue;
            }

            let q = i - 1;
            s += nums[i] as i64;
            i += 1;
            let mut mx = 0i64;
            let mut t = 0i64;
            while i < n && nums[i - 1] < nums[i] {
                t += nums[i] as i64;
                i += 1;
                mx = mx.max(t);
            }
            s += mx;

            mx = 0;
            t = 0;
            let mut j = p as isize - 2;
            while j >= l as isize {
                t += nums[j as usize] as i64;
                mx = mx.max(t);
                j -= 1;
            }
            s += mx;

            ans = ans.max(s);
            i = q;
        }
        ans
    }
}

评论