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

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

/*
 * @lc app=leetcode.cn id=1186 lang=typescript
 *
 * [1186] 删除一次得到子数组最大和
 */

// @lc code=start
function maximumSum(arr: number[]): number {}
// @lc code=end

解法 1: 前缀和

function maximumSum(arr: number[]): number {
  const n = arr.length
  let max = Math.max(...arr),
    min = 0,
    sums: number[] = []

  for (let i = 0; i < n; i++) {
    sums[i] = (sums[i - 1] ?? 0) + arr[i]
    max = Math.max(max, sums[i] - min)
    min = Math.min(min, sums[i])
  }
  const l: number[] = [],
    r: number[] = []
  {
    let max = -Infinity,
      min = 0
    for (let i = 0; i < n; i++) {
      min = Math.min(min, sums[i])
      l[i] = min
    }
    for (let i = n - 1; i >= 0; i--) {
      max = Math.max(max, sums[i])
      r[i] = max
    }
  }
  if (n > 1) max = Math.max(max, r[n - 1] - (l[n - 3] ?? 0) - arr[n - 1])
  for (let i = 0; i < n - 1; i++) {
    max = Math.max(max, r[i + 1] - (l[i - 1] ?? 0) - arr[i])
  }
  return max
}

Case

test.each([
  { input: { arr: [2, 1, -2, -5, -2] }, output: 3 },
  { input: { arr: [1, -2, 0, 3] }, output: 4 },
  { input: { arr: [1, -2, -2, 3] }, output: 3 },
  { input: { arr: [-1, -1, -1, -1] }, output: -1 },
])('input: arr = $input.arr', ({ input: { arr }, output }) => {
  expect(maximumSum(arr)).toEqual(output)
})