Daily Dose of DSA - Day 20

Question Link : https://www.codingninjas.com/studio/problems/maximum-sum-of-non-adjacent-elements_843261?leftPanelTab=0

Using Recursive DP:

1. The rec function recursively calculates the maximum sum from index 0 to index ind while ensuring that adjacent elements are not taken into account.

2. The function receives three parameters: index, nums, and dp. index represents the current index being considered, nums is the input vector, and dp is a dynamic programming array used to store the maximum sum of non-adjacent elements up to each index.

3. The base cases are handled within the function:

   • If index is 0, it means we have reached the first element. In this case, the function simply returns the value of nums[index].

   • If index is less than 0, it means we have gone beyond the range of the vector. In this case, the function returns 0.

   • If the maximum sum for the current index has already been calculated (stored in dp[index]), the function directly returns it.

4. Inside the function, two variables x and y are initialized. x represents the maximum sum when including the current element nums[index] and skipping the adjacent element, which is obtained by recursively calling rec with index-2. y represents the maximum sum obtained by excluding the current element, which is obtained by recursively calling rec with index-1.

5. The function returns the maximum value between x and y and stores it in dp[index].

6. The maximumNonAdjacentSum function initializes the dp vector with size n and calls the rec function starting from the last index (n-1).

7. Finally, the function returns the maximum sum of non-adjacent elements, which is stored in dp[n-1].

In summary, the code recursively finds the maximum sum of non-adjacent elements in the given nums vector. It uses dynamic programming by storing the calculated values in the dp vector to avoid redundant computations. The final result is the maximum sum of non-adjacent elements in the vector, which is returned by the maximumNonAdjacentSum function.

#include <bits/stdc++.h>
// rec(ind)->maximum sum from index = 0 to index = ind ()
// without taking adjacent elements
int rec(int index, vector<int> &nums, vector<int> &dp)
{
     if (index == 0)
          return nums[index];
     if (index < 0)
          return 0;
     if (dp[index] != -1)
          return dp[index];

     int x = nums[index] + rec(index - 2, nums, dp);
     int y = rec(index - 1, nums, dp);

     return dp[index] = max(x, y);
}

int maximumNonAdjacentSum(vector<int> &nums)
{

     int n = (int)nums.size();
     vector<int> dp(n, -1);
     return rec(n - 1, nums, dp);
}

Using Iterative DP:

1. The rec function iteratively calculates the maximum sum of non-adjacent elements up to a specific index.

2. The function receives three parameters: index, nums, and dp. index represents the current index being considered, nums is the input vector, and dp is a dynamic programming array used to store the maximum sum of non-adjacent elements up to each index.

3. The base cases are handled within the function:

   • dp[0] is set to nums[0] since the maximum sum up to the first element is the element itself.

   • dp[1] is set to the maximum value between nums[1] and nums[0] since the maximum sum up to the second element is the maximum value of either the first or second element.

4. Inside the loop starting from index 2, two variables x and y are calculated. x represents the maximum sum when including the current element nums[index] and skipping the adjacent element, which is obtained by adding nums[index] with the maximum sum up to two indices back (dp[index-2]). y represents the maximum sum obtained by excluding the current element, which is the maximum sum up to the previous index (dp[index-1]).

5. The function assigns the maximum value between x and y to dp[index], storing the maximum sum of non-adjacent elements up to the current index.

6. The maximumNonAdjacentSum function initializes the dp vector with size n and calls the rec function starting from the last index (n-1).

7. Finally, the function returns the maximum sum of non-adjacent elements, which is stored in dp[n-1].

In summary, the code iteratively finds the maximum sum of non-adjacent elements in the given nums vector. It uses dynamic programming by iteratively calculating the maximum sum up to each index and storing the results in the dp vector. The final result is the maximum sum of non-adjacent elements, which is returned by the maximumNonAdjacentSum function.

#include <bits/stdc++.h>
void rec(int index, vector<int> &nums, vector<int> &dp)
{
     int n = (int)nums.size();
     int x, y;
     dp[0] = nums[0];
     dp[1] = max(nums[1], nums[0]);
     for (index = 2; index < n; index++)
     {
          x = nums[index] + dp[index - 2];
          y = dp[index - 1];

          dp[index] = max(x, y);
     }
}

int maximumNonAdjacentSum(vector<int> &nums)
{

     int n = (int)nums.size();
     vector<int> dp(n, -1);
     rec(n - 1, nums, dp);
     return dp[n - 1];
}

Space Optimization in Iterative DP :

1. The rec function iteratively calculates the maximum sum of non-adjacent elements up to a specific index.

2. The function receives two parameters: index and nums. index represents the current index being considered, and nums is the input vector.

3. Inside the function, the size of the nums vector is obtained and stored in n.

4. Two variables x and y are initialized. x represents the maximum sum when including the current element nums[index] and skipping the adjacent element, which is obtained by adding nums[index] with the previous two elements' maximum sum (prev2). y represents the maximum sum obtained by excluding the current element, which is the previous maximum sum (prev1).

5. The function calculates the maximum value between x and y and assigns it to a new variable curr. Then, it updates prev2 with the previous maximum sum (prev1) and prev1 with the current maximum sum (curr).

6. The loop continues for the remaining elements of the nums vector, updating prev2 and prev1 in each iteration.

7. The function returns prev1, which represents the maximum sum of non-adjacent elements.

8. The maximumNonAdjacentSum function initializes the n variable with the size of the nums vector and calls the rec function starting from the last index (n-1).

9. Finally, the function returns the maximum sum of non-adjacent elements, which is obtained from the rec function.

In summary, the code iteratively finds the maximum sum of non-adjacent elements in the given nums vector. It uses two variables (prev2 and prev1) to keep track of the previous two maximum sums while traversing the vector. By updating these variables in each iteration, the function finds the maximum sum efficiently. The final result is the maximum sum of non-adjacent elements, which is returned by the maximumNonAdjacentSum function.

#include <bits/stdc++.h>
int rec(int index, vector<int> &nums)
{
     int n = (int)nums.size();
     int x, y;
     int prev2 = nums[0];
     int prev1 = max(nums[1], nums[0]);
     for (index = 2; index < n; index++)
     {
          x = nums[index] + prev2;
          y = prev1;

          int curr = max(x, y);
          prev2 = prev1;
          prev1 = curr;
     }

     return prev1;
}

int maximumNonAdjacentSum(vector<int> &nums)
{

     int n = (int)nums.size();

     return rec(n - 1, nums);
}