LeetCode 1186. 删除一次得到子数组最大和

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 1186. 删除一次得到子数组最大和

思路分析

解法一：动态规划（推荐）

核心思路：

dp0 表示以当前位置结尾且未删除元素的最大子数组和。

dp1 表示以当前位置结尾且已删除一个元素的最大子数组和。

转移：dp0 = max(dp0 + a[i], a[i])，dp1 = max(dp1 + a[i], dp0_prev)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int maximumSum(int[] arr) {
        int dp0 = arr[0];
        int dp1 = Integer.MIN_VALUE / 2;
        int best = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int prev0 = dp0;
            dp0 = Math.max(dp0 + arr[i], arr[i]);
            dp1 = Math.max(dp1 + arr[i], prev0);
            best = Math.max(best, Math.max(dp0, dp1));
        }

        return best;
    }
}

func maximumSum(arr []int) int {
	dp0 := arr[0]
	dp1 := -1 << 60
	best := arr[0]

	for i := 1; i < len(arr); i++ {
		prev0 := dp0
		if dp0+arr[i] > arr[i] {
			dp0 = dp0 + arr[i]
		} else {
			dp0 = arr[i]
		}

		if dp1+arr[i] > prev0 {
			dp1 = dp1 + arr[i]
		} else {
			dp1 = prev0
		}

		if dp0 > best {
			best = dp0
		}
		if dp1 > best {
			best = dp1
		}
	}

	return best
}

相似题目

题目	难度	考察点
1186. 删除一次得到子数组最大和	中等	DP
53. 最大子数组和	简单	DP
152. 乘积最大子数组	中等	DP
1749. 任意子数组和的绝对值的最大值	中等	前缀和
1567. 乘积为正数的最长子数组长度	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/31640381