## Table of contents

- Given problem
- Using brute force algorithm
- Using prefix sum technique
- Using binary search algorithm
- Using Kadane algorithm
- Wrapping up

## Given 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 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
```

## Using brute force algorithm

From the requirements, we can find that the step by step sum of the **startValue** and all elements of an array is never less than 1.

So, we will choose the initial value of **startValue** = 1.

For each sum of **startValue** and elements of an array is less than 1, exit the loop. Otherwise, immediately return the value of **startValue**.

```
public int minStartValue(int[] nums) {
int minStartValue = 1;
while (true) {
int startValue = minStartValue;
boolean isMinValue = true;
for (int i = 0; i < nums.length; ++i) {
startValue += nums[i];
if (startValue < 1) {
isMinValue = false;
break;
}
}
if (isMinValue) {
return minStartValue;
}
++minStartValue;
}
}
```

## Using prefix sum technique

Before jump directly into source code of this section, we need to read an article about Prefix sum.

The idea here is that we will calculate the sum of elements at specific index, then we will find the minimum sum in prefix sum array.

And the minimum value of start value that satisfies **start value + minimum sum = 1**.

```
public int minStartValue(int[] nums) {
int[] prefixSum = new int[nums.length];
prefixSum[0] = nums[0];
int minSum = prefixSum[0];
for (int i = 1; i < nums.length; ++i) {
prefixSum[i] += prefixSum[i - 1] + nums[i];
minSum = Math.min(minSum, prefixSum[i]);
}
return 1 - minSum < 1 ? 1 : 1 - minSum;
}
```

## Using binary search algorithm

Our idea is that we need to find the value of **startValue** variable from 1 to N. It means that its value is belong to a sorted array. So we can use Binary Search for this problem.

## Using Kadane algorithm

## Wrapping up

- Identify some particular traits to apply algorithms, techniques such as prefix sum, binary search, kadane algorithm.

Refer:

https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/