Skip to content

Latest commit

 

History

History
118 lines (107 loc) · 3.53 KB

1425. Constrained Subsequence Sum.md

File metadata and controls

118 lines (107 loc) · 3.53 KB

1425. Constrained Subsequence Sum

Difficulty : Hard

Related Topic : Dynamic Programming

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Solution

  • mine
    • Java

      • DP Time Limited

        // O(L * Min(K, L))time
// O(L)space
public int constrainedSubsetSum(int[] nums, int k) {
    int l = nums.length;
    int[] dp = new int[l + 1];
    dp[0] = Integer.MIN_VALUE;
    int res = Integer.MIN_VALUE;;
    for(int i = 1; i <= l; i++){
        dp[i] = nums[i - 1];
        for(int j = 1; j <= k && i - j > 0; j++){
            dp[i] = Math.max(dp[i], nums[i - 1] + dp[i - j]);
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

      • DP + Sliding Window Runtime: 15 ms, faster than 82.46%,Memory Usage: 48 MB, less than 68.50% of Java online submissions

        same as 1499. Max Value of Equation.

        // O(L)time
// O(L)space
public int constrainedSubsetSum(int[] nums, int k) {
    int l = nums.length;
    int res = Integer.MIN_VALUE;
    int[] record = new int[l];
    LinkedList<Integer> list = new LinkedList<>();
    for (int i = 0; i < l; i++) {
        while (!list.isEmpty() && i - list.getFirst() > k) {
            list.removeFirst();
        }
        record[i] = nums[i];
        if (!list.isEmpty()) {
            record[i] = Math.max(record[i], nums[i] + record[list.getFirst()]);
        }
        res = Math.max(res, record[i]);
        while (!list.isEmpty() && record[list.getLast()] <= record[i]) {
            list.removeLast();
        }
        list.add(i);
    }
    return res;
}
  • the most votes
    • Runtime: 23 ms, faster than 32.37%, Memory Usage: 60.6 MB, less than 9.79% of Java online submissions 
      public int constrainedSubsetSum(int[] A, int k) {
    int res = A[0];
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < A.length; ++i) {
        A[i] += !q.isEmpty() ? q.peek() : 0;
        res = Math.max(res, A[i]);
        while (!q.isEmpty() && A[i] > q.peekLast())
            q.pollLast();
        if (A[i] > 0)
            q.offer(A[i]);
        if (i >= k && !q.isEmpty() && q.peek() == A[i - k])
            q.poll();
    }
    return res;
}