给你一个整数数组 nums 。

你可以从数组 nums 中删除任意数量的元素，但不能将其变为 空 数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组：

  1. 子数组中的所有元素 互不相同 。

  2. 最大化 子数组的元素和。

返回子数组的 最大元素和 。

子数组是数组的一个连续、非空的元素序列。

示例 1：

输入：nums = [1,2,3,4,5]

输出：15

解释：

不删除任何元素，选中整个数组得到最大元素和。

示例 2：

输入：nums = [1,1,0,1,1]

输出：1

解释：

删除元素 nums[0] == 1、nums[1] == 1、nums[2] == 0 和 nums[3] == 1 。选中整个数组 [1] 得到最大元素和。

示例 3：

输入：nums = [1,2,-1,-2,1,0,-1]

输出：3

解释：

删除元素 nums[2] == -1 和 nums[3] == -2 ，从 [1, 2, 1, 0, -1] 中选中子数组 [2, 1] 以获得最大元素和。

提示：

  • 1 <= nums.length <= 100

  • -100 <= nums[i] <= 100

思路

  • 记录正数是否出现，没出现过则进行累加

  • 扩展——只能删除负数

  • 扩展——只能删除负数或0

代码

  • 记录正数是否出现，没出现过则进行累加

class Solution {
    public int maxSum(int[] nums) {
        int result = 0;
        boolean[] flags = new boolean[101];
        int neg = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > 0 && !flags[num]) {
                result += num;
                flags[num] = true;
            } else {
                neg = Math.max(neg, num);
            }
        }
        return result == 0 ? neg : result;
    }
}

  • 扩展，只能删除负数

class Solution {
    public int maxSum(int[] nums) {
        int result = -1;
        boolean[] flags = new boolean[101];
        int sum = 0;
        int neg = Integer.MIN_VALUE;
        int start = 0;
        for (int num : nums) {
            if (num > -1) {
                while (flags[num]) {
                    if (nums[start] > -1) {
                        sum -= nums[start];
                        flags[nums[start]] = false;
                    }
                    start++;
                }
                sum += num;
                result = Math.max(result, sum);
                flags[num] = true;
            } else {
                neg = Math.max(neg, num);
            }
        }
        return result == -1 ? neg : result;
    }
}

  • 扩展，只能删除负数或0

class Solution {
    public int maxSum(int[] nums) {
        int result = -1;
        boolean[] flags = new boolean[101];
        int sum = 0;
        int neg = Integer.MIN_VALUE;
        int start = 0;
        for (int num : nums) {
            if (num > 0) {
                while (flags[num]) {
                    if (nums[start] > -1) {
                        sum -= nums[start];
                        flags[nums[start]] = false;
                    }
                    start++;
                }
                sum += num;
                result = Math.max(result, sum);
                flags[num] = true;
            } else {
                neg = Math.max(neg, num);
            }
        }
        return result == -1 ? neg : result;
    }
}