Leetcode 2708. Maximum Strength of a Group

[Woodyiiiiiii]

2708. Maximum Strength of a Group

2708. Maximum Strength of a Group
O(2^N) 状压DP

这道题，我一看到数据范围，就觉得不需要记忆化搜索，直接暴力递归即可。不过，这道题想记忆化搜索都不需要。其实，这样子时间复杂度是2^n，因为类似一个二叉树结构，选或者不选。

接着，看到是乘法， 且存在负数，top-down返回的最大值与当前值不一定能组成最大值，所以top-down也要返回最小值，以防负数的出现。同时也要跟当前值做比较进行取舍。

class Solution {
    int n;
    int[] nums;

    public long maxStrength(int[] nums) {
        n = nums.length;
        this.nums = nums;
        long[] ans = dfs(0);
        return ans[1];
    }

    private long[] dfs(int i) {
        if (i >= n) {
            return new long[]{1, 1};
        }
        long[] next = dfs(i + 1);
        long max = Math.max(Math.max(i == n - 1 ? -10 : next[1], i == n - 1 ? -10 : next[0]), Math.max(nums[i] * next[0], nums[i] * next[1]));
        max = Math.max(max, nums[i]);
        long min = Math.min(Math.min(i == n - 1 ? 10 : next[1], i == n - 1 ? 10 : next[0]), Math.min(nums[i] * next[0], nums[i] * next[1]));
        min = Math.min(min, nums[i]);
        return new long[]{min, max};
    }
}

那么其实还有O(nlgn)甚至O(n)的解法——贪心。正值肯定都取，负数要取最小的偶数个，0的话看情况取。注意corn case。

class Solution {
    public long maxStrength(int[] nums) {
        if (Arrays.stream(nums).allMatch(num -> num == 0)) {
            return 0;
        }
        long ans = 1;
        int negativeCount = 0, positiveCount = 0;
        for (int num : nums) {
            if (num > 0) {
                ans *= num;
                positiveCount ++;
            } else if (num < 0) {
                negativeCount ++;
            }
        }
        Arrays.sort(nums);
        if (negativeCount % 2 == 0) {
            for (int num : nums) {
                if (num < 0) {
                    ans *= num;
                }
            }
        } else {
            int cnt = negativeCount - 1;
            for (int num : nums) {
                if (cnt == 0) {
                    break;
                }
                if (num < 0) {
                    ans *= num;
                    cnt--;
                }
            }
        }
        
        if (positiveCount == 0 && negativeCount == 1) {
            ans = nums.length == 1 ? nums[0] : 0;
        }

        return ans;
    }
}