LeetCode.S1413

LeetCode.S1413 题目：

题目大意：

给定一个数组，找到一个数res，将res作为前缀和的初始值，使得数组前缀和的每一项都大于等于1，输出最小的k。

数据范围：

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

思路：

求出前缀和的最小值s，如果s小于1，则res = abs(s) + 1，否则s = 1。

代码：

import java.util.Arrays;

class Solution {
    public int minStartValue(int[] nums) {
        int[] sums = new int[110];
        int res = 1;
        for (int i = 1; i <= nums.length; i ++ ){
            sums[i] = sums[i - 1] + nums[i - 1];
            if (sums[i] < 0){
                res = Math.max(res, Math.abs(sums[i]) + 1);
            }
        }
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{1, -2, -3};
        System.out.println(solution.minStartValue(nums));

    }
}

时空复杂度分析：

时间复杂度 : O(n)
空间复杂度 : O(n)，可简化为O(1)

题目链接：

[1413. 逐步求和得到正数的最小值 - 力扣（LeetCode）](

LeetCode.S1413

Java相关栏目本月热门文章