LeetCode 1755. Closest Subsequence Sum
Brute Force + Binary Search + Meet in the Middle
You are given an integer array nums
and an integer goal
.
You want to choose a subsequence of nums
such that the sum of its elements is the closest possible to goal
. That is, if the sum of the subsequence's elements is sum
, then you want to minimize the absolute difference abs(sum - goal)
.
Return the minimum possible value of abs(sum - goal)
.
Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.
Example 1:
Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.
Example 2:
Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.
Example 3:
Input: nums = [1,2,3], goal = -7
Output: 7
Constraints:
1 <= nums.length <= 40
-107 <= nums[i] <= 107
-109 <= goal <= 109
Solution:
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
auto cmp = [](const vector<int>& lhs, const vector<int>& rhs) {
return lhs[1] < rhs[1];
};
sort(events.begin(), events.end(), cmp);
int n = events.size();
vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
for (int i = 1; i <= n; i++) {
int non_overlap_index = 0;
for (int l = i - 1; l >= 1; l--) {
if (events[l-1][1] < events[i-1][0]) {
non_overlap_index = l;
break;
}
}
for (int j = 1; j <= k; j++) {
dp[i][j] = max(dp[non_overlap_index][j-1] + events[i-1][2], dp[i-1][j]);
}
}
return dp[n][k];
}
};
PreviousLeetCode 1754. Largest Merge Of Two StringsNextLeetCode 1760. Minimum Limit of Balls in a Bag
Last updated
Was this helpful?