当前位置:网站首页>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
边栏推荐
猜你喜欢
随机推荐
关于JWT 和Token(转)
Dijkstra求最短路
一文教会你快速上手 Vim
所谓软件测试工作能力强,其实就是这 5 点
使用flink-sql写入mysql的时候,只指定插入的字段,但是会报错id字段错误,没有默认值,创
charles的功能操作
Kotlin协程:父子协程的绑定与传递
如何快速成为一名软件测试工程师?测试员月薪15k需要什么技术?
Shell 文本三剑客 awk
goland console shows overlapping problem solution
The same is a primary test, why does he pay 5,000 yuan more than me?
快35了,还在“点点点”?那些入行几年的测试点工后来都怎么样了?
cuda——nms
金融口译,口译中金融高频词有哪些
2022/08/09 学习笔记 (day26) IO流
Pen paper records
WPF 实现更换主题色
flutter 创建可增型列表和列表排序
二维空间下的向量旋转
BFF避坑指南








