2708.一个小组的最大实力值

【LetMeFly】2708.一个小组的最大实力值：O(n)一次遍历

力扣题目链接：https://leetcode.cn/problems/maximum-strength-of-a-group/

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

 

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

 

提示：

• 1 <= nums.length <= 13
• -9 <= nums[i] <= 9

解题方法：一次遍历

非常小的负数（绝对值非常大）乘以一个负整数就变成了非常大的数；非常大的正数乘以一个正整数也是非常大的数。

有没有发现，我们只需要考虑最大的数和最小的数就可以了。

因此只需要遍历一次数组，遍历的过程中使用两个变量$M$和$m$分别维护当前最大值和最小值。更新公式：

$$
new_m = \min{m, nums[i], m\times nums[i], M\times nums[i]} \
new_M = \max{M, nums[i], m\times nums[i], M\times nums[i]}
$$

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

// 9^{13} = 2541865828329
class Solution {
public:
    ll maxStrength(vector<int>& nums) {
        ll m = nums[0], M = m;
        for (int i = 1; i < nums.size(); i++) {
            ll newm = min({m, (ll)nums[i], m * nums[i], M * nums[i]});
            ll newM = max({M, (ll)nums[i], m * nums[i], M * nums[i]});
            m = newm, M = newM;
        }
        return M;
    }
};

Python

from typing import List

class Solution:
    def maxStrength(self, nums: List[int]) -> int:
        M, m = nums[0], nums[0]
        for i in range(1, len(nums)):
            M, m = max(M, nums[i], M * nums[i], m * nums[i]), \
                   min(m, nums[i], M * nums[i], m * nums[i])
        return M

Java

class Solution {
    public long maxStrength(int[] nums) {
        long m = nums[0], M = nums[0];
        for (int i = 1; i < nums.length; i++) {
            long newm = Math.min(m, Math.min((long)(nums[i]), Math.min(m * nums[i], M * nums[i])));
            long newM = Math.max(M, Math.max((long)(nums[i]), Math.max(m * nums[i], M * nums[i])));
            m = newm;
            M = newM;
        }
        return M;
    }
}

Go

package main

func min(a int64, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

func min4(a int64, b int64, c int64, d int64) int64 {
    return min(a, min(b, min(c, d)))
}

func max(a int64, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func max4(a int64, b int64, c int64, d int64) int64 {
    return max(a, max(b, max(c, d)))
}

func maxStrength(nums []int) int64 {
    m, M := (int64)(nums[0]), int64(nums[0])
    for i := 1; i < len(nums); i++ {
        m, M = min4(m, (int64)(nums[i]), m * (int64)(nums[i]), M * (int64)(nums[i])),
               max4(M, (int64)(nums[i]), m * (int64)(nums[i]), M * (int64)(nums[i]))
    }
    return M
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141884725