头像

DongPPman




离线:8小时前


最近来访(2)
用户头像
翩竹
用户头像
Coderoger


给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素,允许剔除一个元素后最大),返回其最大和。

输入:nums = [7, 9, -100, 5, 3, -10, 50, -300, 300, -100, 110]
输出:410 

输入:nums = [-1, -10]
输出:-1

我是想的是设置dp[i]表示前n个数剔除最小的负数的,最大和,但是写的不太对,有人教教吗...

int maxsub(int[] nums) {
        int[] dp = new int[nums.length + 1];
        //dp[i]表示前i个数,剔除一个最小的负数的情况.
        int numtmp = 0;
        dp[0] = 0;
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= nums.length; i++) {
            if (nums[i - 1] < numtmp) {
                dp[i] = dp[i - 1] + numtmp;
                numtmp = nums[i - 1];
            } else {
                dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1];
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
    public static void main(String[] args) {
        int []nums= {7, 9, -100, 5, 3, -10, 50, -300, 300, -100, 110};
        System.out.println(meiriyouxian.maxsub(nums));
    }