Problem Link  Tasty Candies
Problem Statement:
Misha LOVES candies, and she wants to maximize her happiness by selecting a subarray of candies, each with a tastiness value and a type (0
or 1
). The goal is to find the maximum sum of tastiness from a contiguous subarray of candies of the same type.
Approach:
The key idea of this solution is to use dynamic programming to find the maximum sum of tastiness for two types of candies (0 and 1). We maintain an array DP
, where DP[i]
represents the maximum sum of tastiness for subarrays ending at index i
.

Input Reading: We read the number of test cases and for each, the number of candies along with their tastiness values and types.

Subarray Separation: Two vectors,
V0
andV1
, store tastiness values based on types (0 and 1) to handle them separately. 
Dynamic Programming Calculation: The function
MaxSumSubarray
calculates the maximum sum for a vector:
If empty, return a very small number.

Initialize
DP[0]
with the first element. Iterate through the vector, updatingDP[i]
to reflect the best subarray sum by either starting fresh or adding to the previous sum. 
Return the maximum from
DP
.


Final Output: Compute maximum happiness for both types and output the larger value.
Time Complexity:
 O(n) per test case, processing each candy once.
Space Complexity:
 O(n) for the DP array and type vectors.