【Hot100】LeetCode—152. 乘积最大子数组

---

题目

• 原题连接：152. 乘积最大子数组

---

1- 思路

动规五部曲

---

2- 实现

⭐152. 乘积最大子数组——题解思路

class Solution {
    public int maxProduct(int[] nums) {
        // 初始化答案以及以第一个元素结尾的最大和最小乘积
        int ans = nums[0];
        int max_i = nums[0];
        int min_i = nums[0];

        // 遍历数组从第二个元素开始
        for (int i = 1; i < nums.length; i++) {
            // 当 nums[i] 为负数时，max_i 和 min_i 需要交换
            if (nums[i] < 0) {
                int temp = max_i;
                max_i = min_i;
                min_i = temp;
            }

            // 更新 max_i 和 min_i
            max_i = Math.max(nums[i], max_i * nums[i]);
            min_i = Math.min(nums[i], min_i * nums[i]);

            // 更新答案
            ans = Math.max(ans, max_i);
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

3- ACM 实现

public class maxProduct {

    public static int maxProduct(int[] nums){
        // 1. 定义dp状态
        int ans = 0;
        // 当前最小值乘积，当前最大乘积
        int maxF = nums[0];
        int minF = nums[0];

        // 2.递推公式
        // 如果 nums[i]<0
        // maxF = Math.max(maxF*nums[i],nums[i]);
        // minF = Math.min(minF*nums[i],nums[i]);


        // 此时 要交换 maxF 和 minF 才能保证乘积最大
        for(int i = 1 ; i < nums.length;i++){
            if(nums[i]<0){
                int tmp = maxF;
                maxF = minF;
                minF = tmp;
            }
             maxF = Math.max(maxF*nums[i],nums[i]);
             minF = Math.min(minF*nums[i],nums[i]);
             ans = Math.max(ans,maxF);
        }
        return ans;
    }



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0 ; i < n;i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("结果是"+maxProduct(nums));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---