This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a simple question 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

4. Comprehensive application

  • Dynamic planning + hash
  • Dynamic programming + recursion
  • .

Leecode 152. Maximum subarray of products

Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

 

Example 1:

Input: [2, 3, 2, 4]

Output: 6

Explanation: the subarray [2,3] has a maximum product of 6.

Example 2:

Input: [- 2, 0, 1]

Output: 0

Explanation: The result cannot be 2 because [-2,-1] is not a subarray.

—

❤ ️ ❤ ️ ❤ ️ ❤ ️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

In this case, we can define a maximum, Max, to be the largest subarray of products

Because we’re dealing with negative numbers, we want to avoid the first negative number, but the second product is positive, and we also need an array with min as the smallest product.

We also need a variable, of course, to record the largest subarray of products, ANS

I’ll just do it one by one.

1.2. Dynamic programming component 2: Transfer equation

Simply put: You need to keep track

The previous product maxcurr, the maximum value of the current value curr and mincurr

The minimum value of the previous product mincurr, the current value curr, and maxcurr

1.3. Dynamic programming component 3: initial conditions and boundary cases

int max = nums[0], min = nums[0], ans = nums[0];

Gets the first value

1.4. Dynamic programming component 4: Order of calculation

In turn, calculate


Stick to getting every medium question right ) 😄 😄 😄 \color{green}{keep on doing every middle question)😄 😄 😄 ~}

Reference code


N I C E 😄 😄 😄 \ color {red} {NICE 😄 😄 😄 ~}

Java version

 class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        returnans; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️