1422.分割字符串的最大得分.md

1422.分割字符串的最大得分

/*
 * @lc app=leetcode.cn id=1422 lang=typescript
 *
 * [1422] 分割字符串的最大得分
 */

// @lc code=start
function maxScore(s: string): number {}
// @lc code=end

解法 1: 一次遍历

假设字符串中 1 的前缀和数组为 $S$,分割位置为 $i$,则当前位置能获得的分数为

$$ \begin{align*} f(i) & = (i+1-s_i)+(s_{n-1}-s_i) \ & = s_{n-1}+(i+1-2s_i) \end{align} $$

其中 $s_{n-1}$ 固定不变,那么要获得最大的分数,只要保证 $i+1-2s_i$ 最大即可.具体的实现用一个 sum 去统计当前前缀和,并用 res 去记录 $i+1-2s_i$ 的最大值,最后相加即可.

function maxScore(s: string): number {
  const n = s.length
  let res = -Infinity,
    sum = 0
  for (let i = 0; i < n; i++) {
    if (s[i] === '1') sum++
    if (i < n - 1) res = Math.max(res, i + 1 - 2 * sum)
  }
  return res + sum
}

Case

test.each([
  { input: { s: '011101' }, output: 5 },
  { input: { s: '00111' }, output: 5 },
  { input: { s: '1111' }, output: 3 },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(maxScore(s)).toEqual(output)
})