题目描述: 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。 代码实现:js 测试样例: 输入:[3,1,2,4,5] 返回值:30 说明: 子数组有 3、1、2、4、5、(3,1)、(3,2)、(3,4)、(3,5)、(1,2)、(1,4)、(1,5)、(2,4)、(2,5)、(4,5)、(3,1,2)、(3,1,4)、(3,1,5)、(3,2,4)、(3,4,5)、(1,2,4)、(1,2,5)、(2,4,5)、(3,1,2,4)、(3,1,2,5)、(3,2,4,5)、(1,2,4,5) 其最小值和是 30
时间: 2023-12-28 10:16:21 浏览: 37
好的,我理解了你的问题。这是一个比较典型的动态规划问题。我们可以定义一个 dp 数组,其中 dp[i] 表示以 nums[i] 结尾的子数组的 min(sub) 之和。那么状态转移方程就是:dp[i] = dp[i - 1] + nums[i] * (i - j + 1) - sum[j - 1],其中 j 是满足 nums[j] > nums[i] 的最大下标,sum[j - 1] 表示 nums[0...j-1] 的和。我们可以通过单调栈来维护 j,时间复杂度为 O(n)。最终的答案就是 dp 数组的所有元素之和。以下是代码实现:
```javascript
function minSubArraySum(nums) {
const n = nums.length;
const dp = Array(n).fill(0);
const stack = [];
let sum = 0;
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
stack.pop();
}
const j = stack.length > 0 ? stack[stack.length - 1] : -1;
dp[i] = dp[i - 1] + nums[i] * (i - j) - (j >= 0 ? sum[j] : 0);
sum[i] = (i > 0 ? sum[i - 1] : 0) + nums[i];
stack.push(i);
}
return dp[n - 1];
}
console.log(minSubArraySum([3,1,2,4,5])); // 30
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)