This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Example 2:

Input: nums = [1] Output: 1Copy the code

Example 3:

Input: nums = [0] Output: 0Copy the code

Example 4:

Input: nums = [-1] Output: -1Copy the code

Example 5:

Input: nums = [-100000] Output: -100000Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Thought analysis

Violent solution, first determine all subarrays, subarrays have start and end subscripts, use a double-layer loop, outer loop I control the start of the subarray, inner loop J control the end of the subarray, get the sum of all subarrays, and take the maximum.

The code shown

public int maxSubArray(int[] nums) {
    int length = nums.length;
    // When the array length is 1, the maximum value is the first value
    if (length == 1)
        return nums[0];
    // Maximum value. Default is the first value
    int maxV = nums[0];
    // The outer loop controls the start of the subarray, and the inner loop controls the end of the subarray
    // Each time a value is obtained, it is compared with the current maximum value and updated
    // Time O(n), space O(1)
    for (int i = 0; i < length; i++) {
        if (nums[i] > maxV)
            maxV = nums[i];
        int total = nums[i];
        for (int j = i + 1; j < length; j++) {
            total += nums[j];
            if(total > maxV) maxV = total; }}return maxV;
}
Copy the code

conclusion

Hold on!!

The official answer key

/** * dynamic programming * maximum subarray determination: nums[I] becomes the largest subarray alone or joins the front subarray, depending on nums[I] and f(i-1)+nums[I] */
public static int maxSubArrayOfficial(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}
Copy the code