查看: 1962| 回复: 1
收起左侧

[动态规划] Leetcode 689 Maximum Sum of 3 Non-Overlapping Subarrays

ThinkDeeper2 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   19
95%
5%
1

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
想写一个Dp 的算法, 试了很多遍,都不能保证全过。求指点。想法就是用4个数组,第一个都是0,第二个是1个subarray 的 sum, 但是只记录到此为止的最大值,如果到此为止的sum是10,但是前面有subarray的sum是20,那么就记录20, 第三个数组记录2 个subarray 的 sum, 很显然 2 个 subarray 相加,这两个Subarray不能overlap. 最后一个dp array 就是三个subarray 的 sum. 同时有一个id的数组记录最大值开始的index.

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        // W is an array of sums of windows
        int[] W = new int[nums.length - k+1]; //if 6 numbers, k=2, W has 5 numbers
        int currSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            if (i >= k) {
                currSum -= nums[i - k];
            }
            if (i >= k - 1) {
                W[i - k + 1] = currSum;
            }
        }

        int[][] dp = new int[4][nums.length-k+2];
        int sum = 0;

        int[][] id = new int[4][nums.length-k+2];
        int max = 0, inId = 0;
        for(int i = 1; i < 4; i++) {
            for(int j = 1; j <= nums.length-k+1; j++) {  //start from index 1 for k=2
                if(j<=k)
                {
                     dp[i][j] = W[0];
                    id[i][j] = 0;
                    continue;
                }

                int tmpmax = W[j-1] + dp[i-1][j-k];
                //w[j-1] is the sum to current j, dp[i-1][j-k] is the best up to j

                if(j - k >= 0) {
                    dp[i][j] = dp[i][j-1];
                    id[i][j] = id[i][j-1];
                }
                if(j > 0 && tmpmax > dp[i][j-1]) {
                    dp[i][j] = tmpmax;
                    id[i][j] = j-1;
                }
            }
        }
        int[] res = new int[3];
        res[2] = id[3][nums.length-k+1];
        res[1] = id[2][res[2] - 1];
        res[0] = id[1][res[1] - 1];        
        return res;
    }
}


上一篇:可以解释一下infrastructure是什么意思吗?
下一篇:【回复就加米】求比较动态规划专题课程
不知道小帅 2020-6-30 10:18:27 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   710
100%
0%
3
本帖最后由 不知道小帅 于 2020-6-30 10:26 编辑

思路应该没问题。但是感觉你的下标是真的有点乱。我用的基本和你一样的方法,但是下标我直接用了所有的。可以给你看一下我写的。
而且既然你想省那么一点空间。。为啥还要对dp和id赋值四个呢。。我被语法搞疯了。这里每次【i】都会自动把后面所有变成斜体。所以下面的p其实是i、
  1. class Solution {
  2.     public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
  3.         int n = nums.length;
  4.         int[] sumK = new int[n];
  5.         int[][] dp = new int[3][n];
  6.         int[][] prev = new int[3][n];
  7.         int sum = 0;
  8.         for (int p = 0; p < k; ++p) {
  9.             sum += nums[p];
  10.         }
  11.         sumK[k - 1] = sum;
  12.         for (int p = k; p < n; ++p) {
  13.             sum += nums[p] - nums[p - k];
  14.             sumK[p] = sum;
  15.         }
  16.         for (int p = 0; p < 3; ++p) {
  17.             int curMax = 0;
  18.             for (int j = (p + 1) * k - 1; j < n; ++j) {
  19.                 if (p == 0) {
  20.                     if (sumK[j] > curMax) {
  21.                         curMax = sumK[j];
  22.                         prev[p][j] = j - k + 1;
  23.                     } else {
  24.                         prev[p][j] = prev[p][j - 1];
  25.                     }
  26.                 } else {
  27.                     if (dp[p - 1][j - k] + sumK[j] > curMax) {
  28.                         prev[p][j] = j - k + 1;
  29.                         curMax = dp[p - 1][j - k] + sumK[j];
  30.                     } else {
  31.                         prev[p][j] = prev[p][j - 1];
  32.                     }
  33.                 }
  34.                 dp[p][j] = curMax;
  35.             }
  36.         }
  37.         int[] ans = new int[3];
  38.         int id = n;
  39.         for (int p = 2; p >= 0; --p) {
  40.             if (id > 0) id = prev[p][id - 1];
  41.             ans[p] = id;
  42.         }
  43.         return ans;
  44.     }
  45. }
复制代码

评分

参与人数 2大米 +5 收起 理由
ThinkDeeper2 + 2 给你点个赞!
14417335 + 3

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表