当前位置:网站首页>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
边栏推荐
猜你喜欢

goland console shows overlapping problem solution

shell文本编辑awk

Mini Program Navigation and Navigation Parameters

Dijkstra求最短路

论文理解:“PIAT: Physics Informed Adversarial Training for Solving Partial Differential Equations“

charles的功能操作

软件测试这些基本类型你知道吗?

Example 044: Matrix Addition

使用curl指令发起websocket请求

嵌入式分享合集32
随机推荐
Small program subcontracting and subcontracting pre-download
HACKTHEBOX——Bank
如何开启热部署Devtools
动态网页开发基础
flutter 制作嵌套列表
元宇宙+NFT是“宝”还是“炒”
Difference between netstat and ss command
软件的生命周期(软件工程各阶段的工作)
金融口译,口译中金融高频词有哪些
程序国际化
Instance 042: Variable scope
【单调栈】【概念讲解&&模板代码】
The so-called software testing ability is actually these 5 points
一个刚入行的测试员怎么样做好功能测试?测试思维真的很重要
从零开始配置 vim(9)——初始配置
驱动程序开发:无设备树和有设备树的platform驱动
js阻止事件冒泡方案
Meteor accelerator Trojan analysis and disposal plan
Do you know these basic types of software testing?
学习总结week4_2正则