首页 > 试题广场 >

01串的价值

[编程题]01串的价值
  • 热度指数：3201 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个只包含 0 和 1 的 01 串 s ，下标从 1 开始，设第 i 位的价值为 vali ，则价值定义如下：

1. i=1时:val1 = 1
2. i>1时：
2.1 若 si ≠ si-1 , vali = 1
2.2 若 si = si-1 , vali = vali-1 + 1
字符串的价值等于 val1 + val2 + val3 + ... + valn

你可以删除 s 的任意个字符，问这个串的最大价值是多少。

输入描述:
第一行一个正整数 n ，代表串长度。
接下来一行一个 01 串 s 。
1 ≤ n ≤ 5,000


输出描述:
输出一个整数代表答案
示例1

输入

6
010101

输出

7

说明

删除后的串为0001或0111时有最大价值
示例2

输入

20
11111000111011101100

输出

94
示例3

输入

4
1100

输出

6
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 9717浏览

热门推荐

通过挑战的用户

相关试题

01串的价值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号