本人小白，初学java，无意中接触到hihocode，看到上面有题目从简到难，手痒故一试。奈何水平有限只能从最简单的题目开始撸起。
首先简单介绍一下该题目：
描述
小Ho给自己定了一个宏伟的目标：连续100天每天坚持在hihoCoder上提交一个程序。100天过去了，小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交，将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡，可以使自己的"最长连续提交天数"最多变成多少天。
输入
第一行是一个整数T(1 <= T <= 10)，代表测试数据的组数。
每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100)，表示第a1, a2, ... aN天小Ho没有提交程序。
输出
对于每组数据，输出通过使用补提交卡小Ho的最长连续提交天数最多变成多少。
样例输入
3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90
样例输出
76
59
100
简单分析一下题目，求最长连续提交天数与求最大子序列问题相同，可以用相同的方法解决问题。
这里我使用了联机算法来计算最大自序和问题（时间复杂度为O（n）），并且对小Ho缺提交的日子赋值为-100，准时提交的日子赋值为1，且使用提交卡覆盖的日子重新赋值为1，这样保证了最大子序和求解出来的值正为题目所求，并且发现使用补提交卡来覆盖未提交日期时，只有覆盖连续的未提交日才有可能出现覆盖后的最大子序和，这样简化了原来的从N个数中将M个数的组合全部列出并求解的困难（其实我并不会写这样穷举的代码，希望大家有会的可以交流一下，虽然这样做的时间复杂度会比我简化问题后的要高= =）。
网友评论