Given an array nums
and an integer target
.
Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target
.
Example 1:
Input: nums = [1,1,1,1,1], target = 2 Output: 2 Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
Example 2:
Input: nums = [-1,3,5,1,4,2,-9], target = 6 Output: 2 Explanation: There are 3 subarrays with sum equal to 6. ([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
Example 3:
Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10 Output: 3
Example 4:
Input: nums = [0,0,0], target = 0 Output: 3
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6
Solution: Prefix Sum + DP
Use a hashmap index to record the last index when a given prefix sum occurs.
dp[i] := max # of non-overlapping subarrays of nums[0~i], nums[i] is not required to be included.
dp[i+1] = max(dp[i], // skip nums[i]
dp[index[sum – target] + 1] + 1) // use nums[i] to form a new subarray
ans = dp[n]
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int maxNonOverlapping(vector<int>& nums, int target) { const int n = nums.size(); vector<int> dp(n + 1, 0); // ans at nums[i]; unordered_map<int, int> index; // {prefix sum -> last_index} index[0] = -1; int sum = 0; for (int i = 0; i < n; ++i) { sum += nums[i]; int t = sum - target; dp[i + 1] = dp[i]; if (index.count(t)) dp[i + 1] = max(dp[i + 1], dp[index[t] + 1] + 1); index[sum] = i; } return dp[n]; } }; |