当前位置:网站首页>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
边栏推荐
猜你喜欢
随机推荐
matlab simulink响应谱计算
小程序wxs
PostgreSQL相关语法及指令示例
二维空间下的向量旋转
goland控制台显示重叠问题解决方案
实测办公场景下,国产远程控制软件的表现力如何?(技术解析)
三极管开关电路参数设计与参数介绍
goland console shows overlapping problem solution
【每日一题】大佬们进来看看吧
uva1392
day17正则表达式作业
学习总结week4_2正则
js原型和原型链以及原型继承
It's almost 35, still "did a little"?What happened to the test workers who had been in the industry for a few years?
NFG电商系统在元宇宙趋势下做什么?
Research on IC enterprises
常用类以及接口
ARP Spoofing - Tutorial Details
二进制与内存
Example 047: Functions Swap Variables









