问个算法问题,康康大家有没有什么好的想法。。。

问个算法问题,康康大家有没有什么好的想法。。。

给一个N个数的混乱序列,序列中最多有N种数字(1 2 3 4 …… N),按顺序分成M组,即每一组数字在序列中必须是连续。

定义一组中不同数字的个数为这一组的值,求M组值的和的最大值。
#笔试题目#
全部评论
回溯(m-1个分割点)+M个计数数组count(int[][] count = new int[m][n+1]),一个differentNumberCount数组,记录每个段里不同数字的个数(在第一次回溯之前便可得到每个段的不同数字个数,后续回溯如果是该段i增加了数字j,则count[i][j]是否等于0,等于0则differentNumberCount[i]+1,否则不变;如果该段i减少了数字j,则先判断count[i][j]是否等于1,如果是则differentNumberCount[i]-1,否则不变。当然,某个段增加或减少数字,对应段的该数字的计数也需要+1或-1)
点赞 回复 分享
发布于 2019-10-18 10:34
诶,这有点像昨天拼多多的题诶!
点赞 回复 分享
发布于 2019-10-18 11:19

相关推荐

评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务