hihocoder入门题目（补提交卡）

本人小白，初学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个数的组合全部列出并求解的困难（其实我并不会写这样穷举的代码，希望大家有会的可以交流一下，虽然这样做的时间复杂度会比我简化问题后的要高= =）。