Leetcode 907 Sum of Subarray Minimums

Problem

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Solution

解题思路

本体的解题方法有多种，不同的解题思路具有不同的时间复杂度。

O(n^2)复杂度解法

此解法是一个简单可行的的算法，具有很小的实现难度，本文在此只略微讲述该算法的设计思路，由于该算法时间复杂度较高，不能在时间限制内跑完所有的Leetcode所有test case，不推荐使用。

本算法中引入两个索引，分别从0n-1，和in-1进行遍历，每次遍历更新当前子序列的最小值并加入最终和中，即可得出求和。还有一个细节需要注意的是，由于数列的最小值和是一个很大的数字，可能会超出int的数值范围(-2^31 ~ 2^31）)，所以需要在循环体中增加对int MAX值/modulo值的比较，保证没有溢出造成结果错误。

另一个O(n^2)复杂度解法

本体也可以用动态规划的思路进行解题。动态规划采用的思想是归纳法思想，将第i规模的问题化简成第i-1规模的问题，由此递推能将问题层层迭套从而减少计算的时间复杂度。 通过公式推导，不难得出，本题长度为n的数列A的解集可以拆分为如下子解集的并集：

f(n) = N(0) U N(1) U ... U N(n-1),
其中N(i)为以A[i]为后缀的所有子序列的min值之集合。

对于N(i)的求解，可以通过如下递归关系得到：

N(i) = { A(i), min(N(i-1), A(i)) }
即包含A(i), N(i-1)中所有元素与A(i)取min值后的集合。

本算法不是最佳解法，实际的比较次数还是O(n^2)复杂度。

O(n)复杂度解法

要想减少元素的比较次数，必须将连续子数组的特性发挥到极致。Leetcode提出了一种寻找以A[i]为最小元素的子数组计数法，也就是说，找到A数组中以每个元素为最小值的子数组个数通过加权求和，就能算出最终答案。

为了找到A数组中以每个元素为最小值的子数组个数，只需要维护一个长度与A等长的数组即可。经过一次遍历，便可以将数组中各个子数组最小值计数完成。因而本算法的时间复杂度为O(n)。

程序设计

本题的算法的关键

实现技巧