Location>code7788 >text

[Ninja algorithm] From the stock market trend to dynamic planning: explore the largest array and problems of the largest sub -array ｜ LeetCode 53 largest sub -array and

Popularity：121 ℃/2025-02-04 20:28:41

From the stock market trend to dynamic planning: explore the largest sub -array and problems

Algorithm in life

Imagine you are a stock trader, and there is a daily daily daily data on the stock. Do you want to find the maximum benefits of which section of continuous trading days. If the stock rose 5 yuan one day, we recorded it at +5 and the drop of 3 yuan was recorded to -3. Finding the largest consecutive trading day is to find the largest sub -array and.

This problem is very common in real life. For example, analyze the fluctuations of user activity, study the maximum accumulation effect of temperature changes, or evaluate the profit performance of enterprises for several months.

Problem description

LeetCode Question 53 The largest sub -array and "described like this: Give you an integer array Nums. Please find out a maximum continuous sub -array (the sub -array contains at least one element) and returns its maximum sum.

For example:

Input: nums = [-2,1, -3,4, -1,2,1, -5,4]
 Output: 6
 Explanation: The sum of the serial array [4, -1,2,1] is 6.

The most intuitive solution: violent enumeration

The easiest way to think of is: to enumerate all possible sub -array, calculate their sum, and find the maximum value.

Let's understand with a simple example:

nums = [1, -2,3, -1]
 Check the sub -array [1]: harmony 1
 Check the sub-array [1, -2]: and -1
 Check the sub-array [1, -2,3]: and 2
 Check the sub-array [1, -2,3, -1]: harmony for 1
 Check the sub-array [-2]: Hesu-2
 ... push according to this
 Find the maximum sum to 3, the corresponding sub -array [3]

Optimized solution: dynamic planning

If you think about it carefully, we will find that when we calculate the maximum array and array at the end of each position, we only need to pay attention to the largest sub -array of the previous position and whether it is worthy of continuing.
Similar to inheritance assets, if the previous inheritance is positive assets, no matter how much or less, there is no better than. On the basis of my previous assets, my current assets or liabilities.
But if the previous inheritance was a liability, then I would rather not choose to start in scratch.

The principle of dynamic planning

  1. Define DP [i] as the largest sub -array and
  2. If the front is a positive number, it is worth continuing; if it is negative, it will start again
  3. Status transfer equation: dp [i] = max (dp [i-1] + nums [i], nums [i])
  4. The final answer is the maximum value in the DP array

Model step demonstration

Demonstrate this process with nums = [1, -2,3, -1]:

1. Treatment 1:
 dp [0] = 1
 The current maximum peace = 1

 2. Treatment-2:
 dp [1] = max (1-2, -2) = -1
 The current maximum peace = 1

 3. Treatment 3:
 dp [2] = max (-1+3, 3) = 3
 The current maximum Harbin = 3

 4. Treatment -1:
 dp [3] = max (3-1, -1) = 2
 The ultimate maximum = 3

Java code implementation

public int MaxSubarray (int [] nums) {
     if (nums == null || == 0) {{
         Return 0;
     }
    
     // dp [i] indicates the maximum array and
     int [] dp = new int [];
     dp [0] = nums [0];
     int maxsum = dp [0];
    
     for (int i = 1; i <; i ++) {
         // Status transfer: either continuing the sum of the front or starting again
         dp [i] = (dp [i-1] + nums [i], nums [i]);
         // Update global maximum sum
         maxsum = (maxsum, dp [i]);
     }
    
     Return maxsum;
 }

Further optimization: space optimization

Observation found that we actually only need the value of the previous state, and we do not need to save the entire DP array.

public int maxSubArray(int[] nums) {
    if (nums == null ||  == 0) {
        return 0;
    }
    
    int currentMax = nums[0];
    int maxSum = nums[0];
    
    for (int i = 1; i < ; i++) {
        currentMax = (currentMax + nums[i], nums[i]);
        maxSum = (maxSum, currentMax);
    }
    
    return maxSum;
}

Comparison

Let's compare these solutions:

Violent enumeration:

  • Time complexity: o (n ：)
  • Space complexity: o (1)
  • Advantages: intuitive and easy to understand
  • Disadvantages: Low efficiency

Dynamic planning:

  • Time complexity: o (n)
  • Space complexity: o (n)
  • Advantages: efficient and easy to understand
  • Disadvantages: need extra space

Space optimization version:

  • Time complexity: o (n)
  • Space complexity: o (1)
  • Advantages: high time and space efficiency are high
  • Disadvantages: Code is not as intuitive as DP several array version

Extended thinking

This topic inspired us:

  1. When encountering the "largest"/"minimum" type, consider dynamic planning
  2. Find the recurrence relationship in the problem
  3. Pay attention to whether it can optimize the space complexity
  4. Pay attention to the negative number

Similar questions are:

  • The best time to buy and sell stocks
  • The maximum number of pensions
  • The maximum sum of the ring array

summary

Through the largest sub -array and this question, we not only learned the solution of a classic dynamic planning problem, but also to understand how to decompose complex issues into child issues, and use the deconstruction of sub -problems to build the final answer. This way of thinking is also very helpful when solving other dynamic planning problems.

Remember, when you need to solve the "maximum continuity and" types of "maximum continuity and" types, dynamic planning can often provide an elegant and efficient solution!

Author: Ninja Algorithm
Public account: Ninja algorithm

I prepared a list of questions and detailed solutions for these questions, covering most of the common test questions. I can say responsiblely that as long as you really master these questions, 80%of algorithm interviews can encounter similar questions. Public account reply [Book of questions] Get ~

<Previous Next>