Question

1413. Minimum Value to Get Positive Step by Step Sum

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def minStartValue(self, nums: List[int]) -> int:
    s, t = 0, inf
    for num in nums:
      s += num
      t = min(t, s)
    return max(1, 1 - t)

class Solution {
  public int minStartValue(int[] nums) {
    int s = 0;
    int t = Integer.MAX_VALUE;
    for (int num : nums) {
      s += num;
      t = Math.min(t, s);
    }
    return Math.max(1, 1 - t);
  }
}

class Solution {
public:
  int minStartValue(vector<int>& nums) {
    int s = 0, t = INT_MAX;
    for (int num : nums) {
      s += num;
      t = min(t, s);
    }
    return max(1, 1 - t);
  }
};

func minStartValue(nums []int) int {
  s, t := 0, 10000
  for _, num := range nums {
    s += num
    if s < t {
      t = s
    }
  }
  if t < 0 {
    return 1 - t
  }
  return 1
}

function minStartValue(nums: number[]): number {
  let sum = 0;
  let min = Infinity;
  for (const num of nums) {
    sum += num;
    min = Math.min(min, sum);
  }
  return Math.max(1, 1 - min);
}

impl Solution {
  pub fn min_start_value(nums: Vec<i32>) -> i32 {
    let mut sum = 0;
    let mut min = i32::MAX;
    for num in nums.iter() {
      sum += num;
      min = min.min(sum);
    }
    (1).max(1 - min)
  }
}

Solution 2

class Solution:
  def minStartValue(self, nums: List[int]) -> int:
    s = list(accumulate(nums))
    return 1 if min(s) >= 0 else abs(min(s)) + 1