1. Topic description

[53Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum. The sample1: Enter nums = [-2.1, -3.4, -1.2.1, -5.4] output:6Continuous subarrays [4, -1.2.1] and maximum, for6. The sample2: Input: nums = [1] output:1The sample3: Input: nums = [0] output:0The sample4: Enter nums = [-1] Output: -1The sample5: Enter nums = [-100000] Output: -100000Tip:1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution. Related Topics Array divide-and-conquer algorithm dynamic planningCopy the code

2. Analysis of ideas

method1

Violent settlement? There’s nothing to say

method2

I was thinking too much about finding the size of the subscript bit to define a dynamically programmed DP array. You can see it as a bad example

method3

I think it’s the best solution. Time complexity = O(n) space complexity O(1), no DP table, but using the essence

You want to know the maximum sum of the entire array. At least one loop is required, and our judgment condition can be understood as if the previous maximum value of the array plus the current value is not greater than the current value, then it is better to calculate and from the current value.

method4

You understand method3, but you define a DP array, which takes up some space

Time complexity = O(n) Space complexity O(n)

3. The AC code

public class No53 {
    public int maxSubArray(int[] nums) {
// return method1(nums);
// return method2(nums);
        return method3(nums);
// return method4(nums);
    }

    /** * Direct violence ** Execution time :133 ms, beating 5.24% of Java users * Memory consumption :38.3 MB, beating 78.36% of Java users *@param nums
     * @return* /
    private int method1(int[] nums) {
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            int tempSum = 0;
            for (int j = i; j < nums.length; j++) {
                tempSum += nums[j];
                if(tempSum > maxSum) { maxSum = tempSum; }}}return maxSum;
    }

    /** * error demonstration ！！！！！ * * Memory Limit Exceeded * *@param nums
     * @return* /
    private int method2(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        if(nums.length == 1) {
            return nums[0];
        }

        int[][] dp = new int[nums.length+1][nums.length+1];
        dp[0] [0] = 0;
        for (int i = 1; i < nums.length+1; i++) {
            dp[i][i] = nums[i-1];
            for (int j = i; j < nums.length+1; j++) {
                dp[i][j] = dp[i][j-1] + nums[j-1];
                int tempSum = dp[i][j];
                if(tempSum > maxSum) { maxSum = tempSum; }}}return maxSum;
    }

    * memory consumption :38.4 MB vs. 60.37% of Java users **@param nums
     * @return* /
    private int method3(int[] nums) {
        int maxSum = nums[0];
        int temp = 0;

        for (int num : nums) {
            // If the sum of the arrays to the current position is less than the current number, recalculate directly from this number
            temp = Math.max(temp+num,num);
            maxSum = Math.max(temp,maxSum);
        }
        return maxSum;
    }
Copy the code

4. To summarize

Product title, product title

According to the actual situation, there is no need to set up a formula for the sake of a formula.

Refer to the content

LeetCode solution – 53. Maximum suborder sum, dynamic programming solution

LeetCode antithesis – | the architectural sequence and (dynamic programming)

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign