Readme

2355.Maximum-Number-of-Books-You-Can-Take

我们令dp[i]表示以i为结尾的区间所能获得的最大值。显然在这个区间里，位置i处一定会取满books[i]。

然后在dp[i]的前提下，我们考察i-1的位置。如果books[i-1] > books[i]-1，根据规则意味着无法取满books[i-1]，且显然，该位置的取值决定于books[i]-1. 类似地，在i-2处，如果books[i-2] > books[i]-2，那么该位置能取的最大值是由books[i]-2决定的。依次往前类推，我们会经历一段逐个减1的等差数列。直至我们发现某处books[j] <= books[i]-(i-j)，那么我们势必会在j处取books[j]，于是自然就有dp[i] = dp[j] + 长度为i-j且公差为1的等差数列之和.

那么对于每个i，我们是否都要靠上述的方法逐一回溯之前的index来确定j的位置呢？实际上，当我们针对某个i确定了j之后，books[j+1:i-1]内的这些元素都可以舍弃不看了。因为未来的任何dp[k]（其中k>i）如果依赖于dp[i]，那么即dp[k] = dp[i] + [i+1:k]的等差数列之和，不需要再计算任何i之前的东西。相反，如果dp[k]不依赖于dp[i]，那么意味着在i的位置上没有取满，自然[j+1:i-1]区间内也不会取满（因为这个区间的books值都高于以books[i]开始从后往前的等差序列）。

所以我们就可以设计一个单调栈。当考察新元素books[i]时，对于栈顶元素j，如果books[j] > books[i]-(i-j)的话，就可以不断退栈：

1. 如果剩余有栈顶元素j，那么dp[i] = dp[j] + area，其中area是长度为L = i-j，最后一个元素是books[i]，公差为1的等差数列之和。于是根据等差数列的求和公式area = (books[i]-L+1 + books[i]) * L /2.
2. 如果剩余没有栈顶元素，那么直接有dp[i] = area，其中area（可能）是长度为i+1，最后一个元素是books[i]，公差为1的等差数列之和。特别注意，等差数列的第一个元素不能小于1。所以，这个等差数列的实际长度应该是L = min(i+1, heights[i]). 于是根据等差数列的求和公式area = (books[i]-L+1 + books[i]) * L /2.

最后返回的是全局dp[i]的最大值。