本文共 986 字,大约阅读时间需要 3 分钟。
给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。
换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦),(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最大的。
注意,删除一个元素后,子数组 不能为空。
输入:arr = [1,-2,0,3]
输出:4 解释:我们可以选出 [1, -2, 0, 3],然后删掉 -2,这样得到 [1, 0, 3],和最大。输入:arr = [1,-2,-2,3]
输出:3 解释:我们直接选出 [3],这就是最大和。输入:arr = [-1,-1,-1,-1]
输出:-1 解释:最后得到的子数组不能为空,所以我们不能选择 [-1] 并从中删去 -1 来得到 0。 我们应该直接选择 [-1],或者选择 [-1, -1] 再从中删去一个 -1。1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4设计两个数组,left和right,左数组统计从0到当前位置最大的和值,右数组统计从最后位置到当前位置的最大和值,然后用数组存left[i - 1] + right[i + 1]的值,找出最大值
左数组统计从0到当前位置最大的和值
for(i = 1; i < arrSize; i++) { left[i] = max(arr[i] + left[i - 1], arr[i]); }
右数组统计从最后位置到当前位置的最大和值
for(j = arrSize - 2; j >= 0; j++) { right[j] = max((arr[j] + right[j - 1], arr[j]); }
用数组存left[i - 1] + right[i + 1]的值
dp[0] = max(left[0], right[-1]); for(k = 1; k < arrSize - 1; k++) { dp[k] = max((left[k] + right[k + 2], dp[k - 1]); }
转载地址:http://twkti.baihongyu.com/