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

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

image.png

Java 题解比较少,分享一下来自一个大佬的第三题的动态规划

public int maximumSum(int[] arr) {
    int ans = arr[0];
    int len = arr.length;
    int[][] dp = new int[len][2];
    // 初始化状态
    // "尚未删除",最大子数组和为本身
    dp[0][0] = arr[0];
    // "已经删除",只能删除自身,最大子数组和为 0
    dp[0][1] = 0;
    for (int i = 1; i < len; i++) {
        // 如果前一个子数组和大于 0,则加上
        dp[i][0] = Math.max(arr[i], arr[i] + dp[i - 1][0]);
        // 删除的字符的两种情况:
        // 1. 当前数字被删除,为了满足至少一个元素,必须加上前面一个子数组 "尚未删除" 的最大值
        // 2. 当前数字不被删除,则由前面子数组删除,前面子数组 "已经删除" 的最大值加上当前数字
        dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
        // 两种状态都可能产生最大值
        ans = Math.max(ans, dp[i][0]);
        ans = Math.max(ans, dp[i][1]);
    }
    return ans;
}

作者:hlxing
链接:https://leetcode-cn.com/circle/article/lwbQfe/
3
展开全部 17 讨论