Compute the Minimum Value to Get Positive Step by Step Sum using

  • 时间:2020-09-09 14:04:20
  • 分类:网络文摘
  • 阅读:83 次

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 1:
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.

step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1  | (5 -3 ) = 2    |  -3
(1 +2 ) = 3  | (2 +2 ) = 4    |   2
(3 -3 ) = 0  | (4 -3 ) = 1    |  -3
(0 +4 ) = 4  | (1 +4 ) = 5    |   4
(4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Example 3:
Input: nums = [1,-2,-3]
Output: 5

Constraints:
1 <= nums.length <= 100
-100 <= nums[i] <= 100

Hints:
Find the minimum prefix sum.

Prefix Sum Algorithm

We can compute the minimal prefix sum using O(N) loop. The final answer is -minSum + 1.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int sum = 0, minsum = 0;
        for (const auto &n: nums) {
            sum += n;
            minsum = min(minsum, sum);
        }
        return -minsum + 1;
    }
};
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int sum = 0, minsum = 0;
        for (const auto &n: nums) {
            sum += n;
            minsum = min(minsum, sum);
        }
        return -minsum + 1;
    }
};

We can also use the std::accumulate to do this:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int minsum = 0;
        std::accumulate(begin(nums), end(nums), 0, [&](auto &a, auto &b) {
            minsum = min(minsum, a + b);
            return a + b;
        });            
        return -minsum + 1;
    }
};
class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int minsum = 0;
        std::accumulate(begin(nums), end(nums), 0, [&](auto &a, auto &b) {
            minsum = min(minsum, a + b);
            return a + b;
        });            
        return -minsum + 1;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
爱之伟大——读《地震中的父与子》有感700字  游泗北新城记作文500字  SEO收录异常诊断:负载均衡架构导致的SEO问题及解决方案  宝塔面板出现漏洞,站长如何做才能让网站更加安全?  掌握这7大SEO优化技巧,提高网站自然排名  网络推广SEO优化是怎么做的?  工信部ICP备案备案系统全新改版,速度更快,用户体验更好  影响网站排名的反向链接细节因素盘点  seo优化六步走网站优化基础策略分享  SEO赚不到钱是病,得治! 
评论列表
添加评论