讨论/题目交流/🏆 第 153 场力扣周赛/
🏆 第 153 场力扣周赛

这是 9 月的第二场周赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验。

image.png

展开讨论
力扣 (LeetCode)发起于 2019-09-08

第三题O(n)做法
分别记录不删除数字和可删除数字的两种Sum

    public int maximumSum(int[] arr) {
        if (arr.length == 0)return 0;
        if (arr.length == 1)return arr[0];

        int sum = 0;
        int res = 0;
        int maxNum = arr[0];

        boolean used = false;
        int useNum = 0;
        int sumRegular = 0;

        for (int i = 0; i < arr.length; i++) {
            maxNum = Math.max(maxNum,arr[i]);

            int cur = arr[i];

            if (cur>=0){
                sum += cur;
                res = Math.max(res,sum);
            }else {
                if (sum+cur>0){
                    sum+=cur;
                    if (!used){
                        sum-=cur;
                        used = true;
                        useNum = cur;
                    }
                    else if (cur<useNum){
                        sum+=useNum;
                        sum-=cur;
                        used = true;
                        useNum = cur;
                    }
                }else {
                    if (sum+useNum>0){
                        used = true;
                        sum = sum+useNum;
                        useNum = cur;
                    }else {
                        used = false;
                        sum = 0;
                    }
                }
                if (sumRegular > sum){
                    sum = sumRegular;
                    used = true;
                    useNum = cur;
                }
            }

            if (sumRegular+cur>0)sumRegular+= cur;
            else sumRegular = 0;
//            System.out.println(cur+"  "+sum+" "+used+" "+useNum+" "+sumRegular);
        }
        if (maxNum<=0)return maxNum;
        return res;
    }
1
展开全部 17 讨论