aboutsummaryrefslogtreecommitdiff
path: root/max_score_split_str.c
diff options
context:
space:
mode:
Diffstat (limited to 'max_score_split_str.c')
-rw-r--r--max_score_split_str.c25
1 files changed, 13 insertions, 12 deletions
diff --git a/max_score_split_str.c b/max_score_split_str.c
index f636fce..533cab0 100644
--- a/max_score_split_str.c
+++ b/max_score_split_str.c
@@ -9,18 +9,19 @@
*/
int maxScore(char *s) {
- int n = strlen(s), ans = 0;
- int *suffix_one = malloc(n * sizeof(int));
- int *prefix_zero = malloc(n * sizeof(int));
- suffix_one[n - 1] = (s[n - 1] == '1');
- for (int i = n - 2; i >= 0; i--)
- suffix_one[i] = suffix_one[i + 1] + (s[i] == '1');
- prefix_zero[0] = (s[0] == '0');
- for (int i = 1; i < n; i++)
- prefix_zero[i] = prefix_zero[i - 1] + (s[i] == '0');
- for (int i = 1; i < n; i++)
- ans = fmax(ans, suffix_one[i] + prefix_zero[i - 1]);
- return ans;
+ int ones = 0, tmp = s[0] == '0' ? 1 : 0, score = tmp;
+ for (int i = 1; i < strlen(s) - 1; ++i) {
+ if (s[i] == '0')
+ tmp++;
+ else {
+ ones++;
+ tmp--;
+ }
+ if (tmp > score)
+ score = tmp;
+ }
+ ones += s[strlen(s) - 1] == '1' ? 1 : 0;
+ return ones + score;
}
int main() {