当前位置:网站首页>1413.Minimum Value to Get Positive Step by Step Sum
1413.Minimum Value to Get Positive Step by Step Sum
2022-08-10 03:18:00 【SUNNY_CHANGQI】
The description of the problem
Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums from left to right.
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
example:
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Explanation: if you choose startValue = 4, in the third iteration your step by step sum is less than 1.
startValue = 4 | startValue = 5 | nums |
---|---|---|
( 4 + ( − 3 ) ) = 1 (4+(-3)) = 1 (4+(−3))=1 | ( 5 + ( − 3 ) ) = 2 (5+(-3)) = 2 (5+(−3))=2 | -3 |
( 1 + 2 ) = 3 (1+2) = 3 (1+2)=3 | ( 2 + 2 ) = 4 (2+2) = 4 (2+2)=4 | 2 |
( 3 − 3 ) = 0 (3-3)=0 (3−3)=0 | ( 4 − 3 ) = 1 (4-3)=1 (4−3)=1 | -3 |
( 0 − 4 ) = 4 (0-4)=4 (0−4)=4 | ( 1 + 4 ) = 5 (1+4)= 5 (1+4)=5 | 4 |
( 4 + 2 ) = 6 (4+2)=6 (4+2)=6 | ( 5 + 2 ) = 7 (5+2)=7 (5+2)=7 | 2 |
The intuition for this
- suppose the tempory summarization is sum
- we get the iterative formula: s t a r t V a l u e − s u m ≥ 1 startValue - sum \geq 1 startValue−sum≥1
- therefore we just find the greatest value in sums composed by 1 − t e m p S u m 1- tempSum 1−tempSum
The codes for this
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int minStartValue(vector<int>& nums) {
int res;
vector<int> sums;
for (int i = 0; i < nums.size(); i++) {
int sum = 0;
for (int j = i; j>=0; j--) {
sum += nums[j];
}
sums.emplace_back(1 - sum);
}
res = *max_element(sums.begin(), sums.end());
return res > 0 ? res : 1;
}
};
int main()
{
Solution s;
vector<int> nums = {
-3, 2, -3, 4, 2};
cout << "minStartValue: " << s.minStartValue(nums) << endl;
return 0;
}
The results
(base) [email protected]-Air testForCpp % ./test
minStartValue: 5
边栏推荐
猜你喜欢
随机推荐
维度表设计
学习总结week4_2正则
vue项目 npm run build 打包项目防止浏览器缓存
Example 047: Functions Swap Variables
Example 048: Number ratio size
二维空间下的向量旋转
一文教会你快速上手 Vim
Example 044: Matrix Addition
【Image Classification】2022-CycleMLP ICLR
电话自动拨号在电脑上自动拨打
MongoDB 常用查询语句
goland console shows overlapping problem solution
WPF 实现更换主题色
golang gin 框架读取无法用 body 传递的表单参数
Flink CDC 2.0及其他数据同步工具对比
flutter异步
请教各位confluence部署连接数据库成功,但是在后面建表设置的时候报错
Day16 charles的基本使用
The so-called software testing ability is actually these 5 points
leetcode-218.天际线问题