当前位置:网站首页>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
边栏推荐
猜你喜欢
嵌入式分享合集32
【CC3200AI 实验教程5】疯壳·AI语音人脸识别(会议记录仪/人脸打卡机)-定时器
ARP欺骗-教程详解
NFG电商系统在元宇宙趋势下做什么?
matlab simulink response spectrum calculation
The same is a primary test, why does he pay 5,000 yuan more than me?
小程序导航及导航传参
动态网页开发基础
Meteor accelerator Trojan analysis and disposal plan
How to write a high-quality test case?
随机推荐
The same is a primary test, why does he pay 5,000 yuan more than me?
netstat和ss命令区别
mediaserver创建
金融口译,口译中金融高频词有哪些
如何使用腾讯字体,已经在什么场合下可以使用该字体?TTTGB-Medium
10个超赞的C语言开源项目,值得学习
一文教会你快速上手 Vim
Mini Program Navigation and Navigation Parameters
golang:base64编解码(转)
BFF避坑指南
【单调栈】【概念讲解&&模板代码】
WPF 实现更换主题色
驱动程序开发:按键中断之异步通知
小程序分包及分包预下载
Robust Real-time LiDAR-inertial Initialization (Real-time Robust LiDAR Inertial Initialization) Paper Learning
proxy代理服务
过水滑环的结构和工作原理
ARP Spoofing - Tutorial Details
Kettle 裁剪表详解(truncate)
HACKTHEBOX——Bank