MaxArray | Go Theme month

[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.

$\color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}$

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

$\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.

—

$\color{green}{keep on doing every middle question)😄 😄 😄 ~}$

Reference code

The language version

func maxProduct(nums []int) int {
    maxF, minF, ans := nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        mx, mn := maxF, minF
        maxF = max(mx * nums[i], max(nums[i], mn * nums[i]))
        minF = min(mn * nums[i], min(nums[i], mx * nums[i]))
        ans = max(maxF, ans)
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}





Copy the code

$\ 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 very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

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

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.