I punch simple algorithm questions | leetcode. Most architectural sequence and [53]

This is the second day of my participation in Gwen Challenge

The original problem

Maximum suborder sum

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.

• 
  $1 <= nums.length <= 3 * 10^4$
• 
  $-10^5 <= nums[i] <= 10^5$

Example 1:

Enter nums = [-2.1, -3.4, -1.2.1, -5.4] output:6Continuous subarrays [4, -1.2.1] and maximum, for6 。
Copy the code

Example 2:

Enter: nums = [1] output:1
Copy the code

Example 3:

Enter: nums = [0] output:0
Copy the code

Example 4:

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

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

jolt

It’s not a quick attack, it’s so hard, fuck.

First look at the problem, the key word is continuous subarrays

violence

Serious people can think of a violent solution. If it’s an array, then you can loop through it to get its contiguous subarrays (you don’t need to pull out all the subarrays, that would be too violent), and write it as a double-layer for loop. The initial value of Max should be small enough not to set 0 to prevent accidents.

int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++)
{
    int sum = 0;
    for (int j = i; j < nums.length; j++)
    {
        sum = sum + nums[j];
        // The sum of contiguous subarrays is the sum of contiguous subarrays
        if(sum > max) max = sum; }}// The value of Max at the end of the loop is the answer to this question
Copy the code

This is the end of the normal situation, but the word is not enough, no way

Dynamic programming

A look at the topic below there is a label [dynamic planning], found that this problem can also use dynamic planning, it does not write I do not know. The main thing is the main thing is here.

Then start to set the dynamic programming topic board to write:

• The boundary conditions

  They say nums.length>=1 so there’s no special boundary here, just remember the first value and use it to extrapit.

  
  $$dp(n)=\left\{ \begin{aligned} nums[0] & &\ n = 1 \\ ??? & & \ n > 1 \\ \end{aligned} \right.$$

• subproblems

  An array of length n whose contiguous subarrays of the largest sum may end in the middle or at both ends. This wave sets the subproblem to the largest subarray ending in nums[I]

  The brain then extrapolates that this is an array of length m (0 < m << n), assuming that the subarray ending in its m-1st element is the largest. So if you go one space behind it, length m plus 1, that’s the sum of the largest contiguous subarrays. It’s going to be associated with the MTH element, which could be larger or smaller than the previous continuous subarray. In this way, there are two results:

  1. Subarray and ratiomBig, continue to compare the firstm + 1An element
  2. Subarray and ratiomSmall, drop the subarray from themElements are accumulated again

  This is the one that you can compute all the way down to m is equal to n. The sum of the subarray left behind is the largest.

• equation

  According to the previous item, it can be obtained as follows:

  
  $$dp(nums[i])=\left\{ \begin{aligned} nums[0] & &\ n = 1 \\ MAX(nums[i], dp[i-1]+nums[i]) & & \ n > 1 \\ \end{aligned} \right.$$

  When nums[I] is traversed, the sum of the largest subarray in dp[I] ending in nums[I] is returned.

• Write code that combines conditions

      public int maxSubArray(int[] nums) {
          // Dynamic programming
          if (nums.length == 1) return nums[0];
          Num [I] = dp[I]
          int[] dp=new int[nums.length];
          dp[0] = nums[0];
          MAX(nums[I], dp[i-1]+nums[I])
          for (int i=1; i<nums.length; i++){ dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
          }
          // Walk through the dp array to find the largest one
          // Set the initial value to the minimum, possibly full of negative numbers
          int res = Integer.MIN_VALUE;
          for (int j : dp) {
              res = Math.max(res, j);
          }
          return res;
      }
  Copy the code

closed

• In fact, that subproblem can be adjustedmIt’s a different way of doing that
• In fact, my answer can be spatially optimized
• Actually, they told us to do divide-and-conquer, but I can’t do that