05 August 2008
从左到右遍历数组，求出让每一步累加都能为正的最小正整数，前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int minStartValue(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int len = nums.length;
int[] preSum = new int[len];
preSum[0] = nums[0];
int minValue = preSum[0];
for (int i = 1; i < len; i++) {
preSum[i] = preSum[i - 1] + nums[i];
minValue = Math.min(minValue, preSum[i]);
}
return minValue < 0 ? (-minValue + 1) : 1;
}
}
压缩空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int minStartValue(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int len = nums.length;
int prePreSum = nums[0];
int minValue = prePreSum;
for (int i = 1; i < len; i++) {
prePreSum += nums[i];
minValue = Math.min(minValue, prePreSum);
}
return minValue < 0 ? (-minValue + 1) : 1;
}
}