thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

class Solution {
    public int MAX_CHUNK;
    public int MINIMUM_REQUIRE_ELEMENT;
    public int maxSum(int[] nums, int k, int m) {
        MAX_CHUNK = k;
        MINIMUM_REQUIRE_ELEMENT = m;
        int[][] memo = new int[nums.length + 1][k + 1];
        for (int i = 0; i <= nums.length; i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
            
        return tryBuildChunk(0, k, nums, memo);
    }
    
    public int tryBuildChunk(int startChunkIdx, int remainChunk, int[] nums, int[][] memo) {
        int n = nums.length;
        if (remainChunk == 0) return 0;

        if (memo[startChunkIdx][remainChunk] != Integer.MIN_VALUE) {
            return memo[startChunkIdx][remainChunk];
        }

        // ignore current index, and the chunk can start by the next element
        int maximumSum = Integer.MIN_VALUE;
        if (n - startChunkIdx >= MINIMUM_REQUIRE_ELEMENT * remainChunk) {
            maximumSum = Math.max(
                maximumSum,
                tryBuildChunk(startChunkIdx + 1, remainChunk, nums, memo)
            );
        }

        // try to make another chunk that start from current idx
        int curChunkSum = 0;
        int lastIdxToBuildValidChunks = n - MINIMUM_REQUIRE_ELEMENT * (remainChunk - 1);
        for (int i = startChunkIdx; i < lastIdxToBuildValidChunks; i++) {
            curChunkSum += nums[i];
            if (i - startChunkIdx + 1 >= MINIMUM_REQUIRE_ELEMENT) {
                maximumSum = Math.max(
                    maximumSum,
                    curChunkSum + tryBuildChunk(i + 1, remainChunk - 1, nums, memo)
                );
            }
        }

        memo[startChunkIdx][remainChunk] = maximumSum;

        return maximumSum;
    }
}

class Solution {
    public long[] findMaxSum(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] map = new int[n][3];
        for(int i =0 ; i< n;i++){
            map[i][0] = nums1[i];
            map[i][1] = nums2[i];
            map[i][2] = i ;
        }
        Arrays.sort(map, (a,b)->a[0]-b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long cur_sum = 0;
        int cnt =0;
        long[] ans = new long[n];
        int last_index= 0;
        for(int i =0 ; i < n ;i++){
            while(map[i][0]>map[last_index][0]){
                cur_sum+=map[last_index][1];
                pq.add(map[last_index][1]);
                last_index++;
            }
            while(pq.size()>k){
                cur_sum-=pq.poll();
            }
            ans[map[i][2]]=cur_sum;
        }
        return ans;
    }
}
©leetcode