7月23日 小红书笔试 3道题解

第1题

生成的数组形如 [k, 2k, 3k, ... , nk]直接等差数列求和就行，模拟也行，反正n规模很小。

记得用long。

第2题

我用滑动窗口做的，先对精华区间进行排序，然后整个sum维护k区间内最多可以访问到的精华区间。

新区间加入时，要把和新区间距离已经超过k的区间给删除掉，然后更新sum。

因为实际sum包括的区间长度可能会大于k，更新ans的时候务必记得sum不一定全部能取到，只能取到区间内k的部分，要加个判断。

评论区有大佬说了，滑动窗口需要从前向后做一次、再从后向前做一次。

第3题

动态规划问题，dp[0]代表原数组的区间和、dp[1] 代表有1个数字变成k之后的区间和，状态转移方程如下：

dp[1] = Math.max(dp[1] + num, Math.max(dp[0] + k, k));
dp[0] = Math.max(dp[0] + num, num);
ans = Math.max(ans, Math.max(dp[0], dp[1]));

记得用long。

8月1日更新：虽然没AK，但还是给面试机会了