DPM10 - Editorial

editorial
, ,
1

Problem Link - Final Solution in Dynamic programming

Problem Statement:

Given N integers, you have to pick a valid subset with the largest sum from these integers.
A valid subset is a subset in which no two adjacent elements are picked.

Approach:

  • We will use a DP array where dp[i] represents the maximum sum of any valid subset that can be formed from the first i integers, respecting the rule that no two adjacent elements are picked.
  • For each integer A[i], we have two options:
    • Include: If we include A[i] in the subset, we cannot include A[i−1], so the total sum will be dp[i−2]+A[i];
    • Exclude: If we exclude A[i], then the total sum will simply be dp[i−1].
  • Therefore, the recurrence relation is dp[i]=max⁡(dp[i−1],dp[i−2]+A[i]). The idea is to make a choice at each position based on the previous computations.
  • The first element’s maximum sum is either 0 (if we don’t select it) or the element itself.
  • For the second element, we can either pick just the second element or stick with the first one.

Complexity:

  • Time Complexity: O(N) Traversing the array once for calculating dp array O(N) and calculating the maximum value for the answer O(N). 2*O(N)->O(N)
  • Space Complexity: O(N) Assigning the dp array with N+1.