diff options
Diffstat (limited to 'max_score_split_str.c')
-rw-r--r-- | max_score_split_str.c | 25 |
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() { |