This is the 20th day of my participation in the August Text Challenge.More challenges in August

preface

The maximum suborder sum of problem 53 is shown as follows:

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 explanation: the maximum sum of consecutive subarrays [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

A, thinking

The maximum suborder and have two comparative messages:

  • Continuous subarray
  • The largest and

I started this problem with a two-layer traversal, and the beat rate was only 7%. So I looked at the official solution, and found that dynamic programming is a very good solution. I’m going to focus on dynamic programming, and two-level traversal is going to be in solution one.

Dynamic programming

The most important point in dynamic programming is that the largest continuous subarray ending at each position is calculated based on the largest subarray at the previous position

Assume that sum[I] is the sum 0 of the largest contiguous subarray ending in I

Sum [I] = Max {sum[I -1] + nums[I], nums[I]}, because nums[I] can either add the preceding segment to the largest subarray, or choose to be the largest subarray by itself.

Sum [I] = Max {sum[I -1] + nums[I], nums[I]} If nums = {-2, 1}, sum[0] = {-2, 1}, sum[0] = {-2, 1}

Sum [1] = nums[1] sum[1] = nums[1]

Through the above steps we found all theiIs the largest subarray sum at the end. Then iterate over the array and return the maximum!

For example

Nums = {-2,1,-3,4,-1,2,1,-5,4} is used as an example

  1. Initialize thesum[0] = nums[0]
  2. throughsum[i] = Math.max(sum[i-1] + nums[i], nums[i])Find allsum[i]. When I’m done walking,sum[] = {-2, 1, -2, 4, 3, 5, 6, 1, 5}
  3. returnsum[]The maximum value of6Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea, although two solutions are provided. But dynamic programming is still recommended!

Double traverse

/** * double loop */
public int maxSubArray(int[] nums) {
    int ret = nums[0];
    int len = nums.length;
    for (int i=0; i<len; i++) {
        int sum = nums[i];
        ret = Math.max(ret, sum);
        for (int j=i+1; j<len; j++) { sum = sum + nums[j]; ret = Math.max(ret, sum); }}return ret;
}
Copy the code

Dynamic programming

    public int maxSubArray(int[] nums) {
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        // Dynamically program to find all maximums ending in I
        for (int i = 1; i<nums.length; i++) {
            sum[i] = Math.max(sum[i-1] + nums[i], nums[i]);
        }
        // Return the maximum value
        int ret = sum[0];
        for (int s : sum) {
            ret = Math.max(s, ret);
        }
        return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {-2.1, -3.4, -1.2.1, -5.4};
        new Number53().maxSubArray(nums);
    }
Copy the code

The results of

Third, summary

If you look closely, you will see that my dynamic programming has one more loop than the official problem solving to find the maximum value in the sum[] array. The official dynamic programming is quite a simplified version (omits the comparison to get the maximum value, and only uses a sum constant to store the size), which is not easy for beginners to understand, so I will not put it up, but also hope to understand!

Thank you to see the end, very honored to help you ~♥