【卡碼網】31. 字符串的最大價值

給定一個字符串 $S$（S.lenth < 5000），只包含 0 和 1 兩個數字，下標從 1 開始，設第 $i$ 位的價值為 $va{l}_i$，則$va{l}_i$的定義如下：

當 i = 1 時：$va{l}_1$ = 1；
當 i > 1 時：
若$S_i$ != $S_{(i?1)}$：$va{l}_i$ = 1，
若$S_i$ == $S_{(i?1)}$：$va{l}_i$ = $va{l}_{(i?1)}$ + 1；

字符串 S 的總價值等于 val1 + val2 + … + valn（n為字符串 S 的長度）。你可以任意刪除字符串 S 中的任意字符，使得字符串 S 的總價值能夠達到最大。

輸入
輸入只有一行，為字符串 S
輸出
輸出一個整數代表答案

樣例輸入

010101

樣例輸出

7

提示
刪除一些字符后，S變為 0001 或 0111 時能夠達到最大價值。

題解

v = v + 1的遞增效果肯定要比 v = 1 強很多，盡可能制造 v = v + 1 的情況，找出所有 0 和 1 的個數, 讓數量多的一方連成塊, 這里得出來的值構成了答案的中間部分，再加上倆邊的不同字符。

這個方案的核心思想是通過計算不同部分連續字符對最終價值的貢獻來得到最大的價值。

核心思路：

首先，使用 count 數組來記錄字符 ‘0’ 和 ‘1’ 的個數。對于每個字符 ‘0’ 和 ‘1’，都分別計算以其為分界的情況下的價值。對于以字符 ‘0’ 為分界的情況：

1. 找到第一個字符 ‘0’ 出現的位置 start 和最后一個字符 ‘0’ 出現的位置 end。
2. 計算連續字符 ‘0’ 所對應的價值：(1 + count[c - ‘0’]) * count[c - ‘0’] / 2，其中 count[c - ‘0’] 是字符 ‘0’ 的個數。也就是將 ‘0’ 之間的所有 ‘1’ 邏輯上刪除。
3. 計算字符 ‘0’ 之前連續字符 ‘1’ 所對應的價值：(1 + start) * start / 2。
4. 計算字符 ‘0’ 之后連續字符 ‘1’ 所對應的價值：(s.length() - end) * (s.length() - end - 1L) / 2，這里要注意長度減1。

同樣的，對于以字符 ‘1’ 為分界的情況，重復上述步驟。最后，從這兩種情況中選擇較大的一個作為最終的最大價值。

import java.lang.*;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine();// count 數組來記錄字符 '0' 和 '1' 的個數int[] count = new int[2];for (char c : s.toCharArray()) {count[c - '0']++;}//對于每個字符 '0' 和 '1'，都分別計算以其為分界的情況下的價值long result = Math.max(getValue('0', s, count), getValue('1', s, count));System.out.println(result);}public static long getValue(char c, String s, int[] count) {//找到第一個字符 '0' 出現的位置 start 和最后一個字符 '0' 出現的位置 end。int start = s.indexOf(c);int end = s.lastIndexOf(c);System.out.println("start: "+start+"\n"+"end: "+end);System.out.println("s.length(): "+s.length());//計算連續字符 '0' 所對應的價值：(1 + count[c - '0']) * count[c - '0'] / 2，其中 count[c - '0'] 是字符 '0' 的個數。也就是將 '0' 之間的所有 ‘1’ 邏輯上刪除。long num = (1L + count[c - '0']) * count[c - '0'] / 2;//計算字符 '0' 之前連續字符 '1' 所對應的價值：(1 + start) * start / 2。num += (1L + start) * start / 2;//計算字符 '0' 之后連續字符 '1' 所對應的價值：(s.length() - end) * (s.length() - end - 1L) / 2，這里要注意長度減1。num += (s.length() - end) * (s.length() - end - 1L) / 2;return num;}
}