CANDY1P - Editorial

editorial
, ,
1

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.

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

  2. Subarray Separation: Two vectors, V0 and V1, store tastiness values based on types (0 and 1) to handle them separately.

  3. 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, updating DP[i] to reflect the best subarray sum by either starting fresh or adding to the previous sum.

    • Return the maximum from DP.

  4. 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.