当前位置:网站首页>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
边栏推荐
猜你喜欢
随机推荐
盘式导电滑环的优点和缺点
获取属性特性几种方法
一个刚入行的测试员怎么样做好功能测试?测试思维真的很重要
全面深入了解什么是反向代理和负载均衡
2022/08/09 学习笔记 (day26) IO流
Flink学习15:Flink自定义数据源
三极管开关电路参数设计与参数介绍
flutter 制作嵌套列表
10个超赞的C语言开源项目,值得学习
Camera partial update
使用注解实现限流
实测办公场景下,国产远程控制软件的表现力如何?(技术解析)
yolov5+usb相机
Difference between netstat and ss command
使用 requestAnimationFrame 提升 web 性能
学习总结week4_2正则
树的介绍、树的定义和基本术语、二叉树的定义和性质、二叉树的顺序表示与实现和链式表示与实现以及树的遍历方法以及两种创建方式
Neo4J 与 Cypher 查询语言基础
MongoDB 常用查询语句
Do you know these basic types of software testing?









