Leetcode 1422 - Maximum Score After Splitting a String

題目

Problem#

給你一個字串 s 你可以把它從任意 index 切成兩半，問你左邊字串 0 的數量與右邊字串 1 的數量相加最大多少？

測資限制#

• $2 \le n \le 500$

想法#

枚舉切割點 $[0, n)$ 去算最大相加 $O(n)$，計算 0 或 1 的數量可以用前綴和，預計算 $O(n)$，每次查詢 $O(1)$

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#