Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5, and 7).
Examples:
Input : arr[] = {3, 5, 3}
Output : 6
Explanation :
Selecting indexes 0 and 2 will maximise the sum
i.e 3+3 = 6
Input : arr[] = {2, 5, 2}
Output : 5
We have already discussed the efficient approach of solving this problem in the previous article.
However, we can also solve this problem using the Dynamic Programming approach.
Dynamic Programming Approach: Let’s decide the states of ‘dp’. Let dp[i] be the largest possible sum for the sub-array starting from index ‘i’ and ending at index ‘N-1’. Now, we have to find a recurrence relation between this state and a lower-order state.
In this case for an index ‘i’, we will have two choices.
1) Choose the current index:
In this case, the relation will be dp[i] = arr[i] + dp[i+2]
2) Skip the current index:
Relation will be dp[i] = dp[i+1]
We will choose the path that maximizes our result.
Thus, the final relation will be:
dp[i] = max(dp[i+2]+arr[i], dp[i+1])
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <bits/stdc++.h>#define maxLen 10using namespace std;// variable to store states of dpint dp[maxLen];// variable to check if a given state// has been solvedbool v[maxLen];// Function to find the maximum sum subsequence// such that no two elements are adjacentint maxSum(int arr[], int i, int n){ // Base case if (i >= n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = 1; // Required recurrence relation dp[i] = max(maxSum(arr, i + 1, n), arr[i] + maxSum(arr, i + 2, n)); // Returning the value return dp[i];}// Driver codeint main(){ int arr[] = { 12, 9, 7, 33 }; int n = sizeof(arr) / sizeof(int); cout << maxSum(arr, 0, n); return 0;} |
Java
// Java program to implement above approach class GFG{static int maxLen = 10;// variable to store states of dp static int dp[] = new int[maxLen]; // variable to check if a given state // has been solved static boolean v[] = new boolean[maxLen]; // Function to find the maximum sum subsequence // such that no two elements are adjacent static int maxSum(int arr[], int i, int n) { // Base case if (i >= n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = true; // Required recurrence relation dp[i] = Math.max(maxSum(arr, i + 1, n), arr[i] + maxSum(arr, i + 2, n)); // Returning the value return dp[i]; } // Driver code public static void main(String args[]){ int arr[] = { 12, 9, 7, 33 }; int n = arr.length; System.out.println( maxSum(arr, 0, n)); }}// This code is contributed by Arnab Kundu |
Python3
# Python 3 program to implement above approachmaxLen = 10# variable to store states of dpdp = [0 for i in range(maxLen)]# variable to check if a given state # has been solvedv = [0 for i in range(maxLen)]# Function to find the maximum sum subsequence# such that no two elements are adjacentdef maxSum(arr, i, n): # Base case if (i >= n): return 0 # To check if a state has # been solved if (v[i]): return dp[i] v[i] = 1 # Required recurrence relation dp[i] = max(maxSum(arr, i + 1, n), arr[i] + maxSum(arr, i + 2, n)) # Returning the value return dp[i]# Driver codeif __name__ == '__main__': arr = [12, 9, 7, 33] n = len(arr) print(maxSum(arr, 0, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to implement above approach using System;class GFG{static int maxLen = 10;// variable to store states of dp static int[] dp = new int[maxLen]; // variable to check if a given state // has been solved static bool[] v = new bool[maxLen]; // Function to find the maximum sum subsequence // such that no two elements are adjacent static int maxSum(int[] arr, int i, int n) { // Base case if (i >= n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = true; // Required recurrence relation dp[i] = Math.Max(maxSum(arr, i + 1, n), arr[i] + maxSum(arr, i + 2, n)); // Returning the value return dp[i]; } // Driver code public static void Main(){ int[] arr = { 12, 9, 7, 33 }; int n = arr.Length; Console.Write( maxSum(arr, 0, n)); }}// This code is contributed by ChitraNayal |
Javascript
<script>// Javascript program to implement above approachvar maxLen = 10;// variable to store states of dpvar dp = Array(maxLen);// variable to check if a given state// has been solvedvar v = Array(maxLen);// Function to find the maximum sum subsequence// such that no two elements are adjacentfunction maxSum(arr, i, n){ // Base case if (i >= n) return 0; // To check if a state has // been solved if (v[i]) return dp[i]; v[i] = 1; // Required recurrence relation dp[i] = Math.max(maxSum(arr, i + 1, n), arr[i] + maxSum(arr, i + 2, n)); // Returning the value return dp[i];}// Driver codevar arr = [12, 9, 7, 33 ];var n = arr.length;document.write( maxSum(arr, 0, n));</script> |
PHP
<?php// PHP program to implement above approach $maxLen = 10; // variable to store states of dp $dp = array_fill(0, $GLOBALS['maxLen'], 0); // variable to check if a given state // has been solved $v = array_fill(0, $GLOBALS['maxLen'], 0); // Function to find the maximum sum subsequence // such that no two elements are adjacent function maxSum($arr, $i, $n) { // Base case if ($i >= $n) return 0; // To check if a state has // been solved if ($GLOBALS['v'][$i]) return $GLOBALS['dp'][$i]; $GLOBALS['v'][$i] = 1; // Required recurrence relation $GLOBALS['dp'][$i] = max(maxSum($arr, $i + 1, $n), $arr[$i] + maxSum($arr, $i + 2, $n)); // Returning the value return $GLOBALS['dp'][$i]; } // Driver code $arr = array( 12, 9, 7, 33 ); $n = count($arr); echo maxSum($arr, 0, $n); // This code is contributed by AnkitRai01?> |
Output
45
Time Complexity : O(n)
Auxiliary Space : O(10)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP of size N+1 to store the solution of the subproblems.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[n-1].
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum subsequence// such that no two elements are adjacentint maxSum(int arr[], int n){ // Base case if (n == 0) return 0; if (n == 1) return arr[0]; if (n == 2) return max(arr[0], arr[1]); // DP table to store solutions to subproblems int dp[n]; // Initializing base cases dp[0] = arr[0]; dp[1] = max(arr[0], arr[1]); // Filling up the DP table using recurrence relation for (int i = 2; i < n; i++) { dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]); } // Returning the final answer return dp[n - 1];}// Driver codeint main(){ int arr[] = { 12, 9, 7, 33 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSum(arr, n) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to find the maximum sum subsequence // such that no two elements are adjacent public static int maxSum(int[] arr, int n) { // Base case if (n == 0) return 0; if (n == 1) return arr[0]; if (n == 2) return Math.max(arr[0], arr[1]); // DP table to store solutions to subproblems int[] dp = new int[n]; // Initializing base cases dp[0] = arr[0]; dp[1] = Math.max(arr[0], arr[1]); // Filling up the DP table using recurrence relation for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]); } // Returning the final answer return dp[n - 1]; } // Driver code public static void main(String[] args) { int[] arr = { 12, 9, 7, 33 }; int n = arr.length; System.out.println(maxSum(arr, n)); }} |
Python3
def maxSum(arr, n): # Base case if n == 0: return 0 if n == 1: return arr[0] if n == 2: return max(arr[0], arr[1]) # DP table to store solutions to subproblems dp = [0] * n # Initializing base cases dp[0] = arr[0] dp[1] = max(arr[0], arr[1]) # Filling up the DP table using recurrence relation for i in range(2, n): dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]) # Returning the final answer return dp[n - 1]arr = [12, 9, 7, 33]n = len(arr)print(maxSum(arr, n)) |
C#
using System;class GFG { // Function to find the maximum sum subsequence // such that no two elements are adjacent static int maxSum(int[] arr, int n) { // Base case if (n == 0) return 0; if (n == 1) return arr[0]; if (n == 2) return Math.Max(arr[0], arr[1]); // DP table to store solutions to subproblems int[] dp = new int[n]; // Initializing base cases dp[0] = arr[0]; dp[1] = Math.Max(arr[0], arr[1]); // Filling up the DP table using recurrence relation for (int i = 2; i < n; i++) { dp[i] = Math.Max(dp[i - 1], arr[i] + dp[i - 2]); } // Returning the final answer return dp[n - 1]; } // Driver code static void Main() { int[] arr = { 12, 9, 7, 33 }; int n = arr.Length; Console.WriteLine(maxSum(arr, n)); }} |
Javascript
// Function to find the maximum sum subsequence// such that no two elements are adjacentfunction maxSum(arr) { // Base cases const n = arr.length; if (n === 0) return 0; if (n === 1) return arr[0]; if (n === 2) return Math.max(arr[0], arr[1]); // DP array to store solutions to subproblems const dp = new Array(n); // Initializing base cases dp[0] = arr[0]; dp[1] = Math.max(arr[0], arr[1]); // Filling up the DP array using recurrence relation for (let i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]); } // Returning the final answer return dp[n - 1];}// Driver codeconst arr = [12, 9, 7, 33];console.log(maxSum(arr)); |
Output
45
Time Complexity : O(n)
Auxiliary Space : O(n)
Another Approach(Using Greedy Strategy):
- Initialize include as the first element and exclude as 0.
- For each element in the array, update include as exclude + current element (considering the current element).
- Update exclude as the maximum of include and exclude (excluding the current element).
- Repeat steps 2 and 3 for all elements in the array.
- Finally, return the maximum of include and exclude as the maximum sum.
Below is the implementation of the above approach:
C++
#include <iostream>#include <algorithm>using namespace std;int maxSumNoAdjacent(int arr[], int n) { if (n == 0) return 0; if (n == 1) return arr[0]; int include = arr[0]; int exclude = 0; for (int i = 1; i < n; i++) { int prevInclude = include; include = exclude + arr[i]; exclude = max(prevInclude, exclude); } return max(include, exclude);}int main() { int arr[] = {12, 9, 7, 33}; int n = sizeof(arr) / sizeof(arr[0]); int maxSum = maxSumNoAdjacent(arr, n); cout<< maxSum << endl; return 0;} |
Java
import java.util.Arrays;public class Main { public static int maxSumNoAdjacent(int[] arr, int n) { if (n == 0) return 0; if (n == 1) return arr[0]; int include = arr[0]; int exclude = 0; for (int i = 1; i < n; i++) { int prevInclude = include; include = exclude + arr[i]; exclude = Math.max(prevInclude, exclude); } return Math.max(include, exclude); } public static void main(String[] args) { int[] arr = {12, 9, 7, 33}; int n = arr.length; int maxSum = maxSumNoAdjacent(arr, n); System.out.println(maxSum); }} |
Python
def maxSumNoAdjacent(arr, n): if n == 0: return 0 if n == 1: return arr[0] include = arr[0] exclude = 0 for i in range(1, n): prevInclude = include include = exclude + arr[i] exclude = max(prevInclude, exclude) return max(include, exclude)arr = [12, 9, 7, 33]n = len(arr)maxSum = maxSumNoAdjacent(arr, n)print(maxSum) |
C#
using System;class Program{ static int MaxSumNoAdjacent(int[] arr, int n) { if (n == 0) return 0; if (n == 1) return arr[0]; int include = arr[0]; int exclude = 0; for (int i = 1; i < n; i++) { int prevInclude = include; include = exclude + arr[i]; exclude = Math.Max(prevInclude, exclude); } return Math.Max(include, exclude); } static void Main() { int[] arr = { 12, 9, 7, 33 }; int n = arr.Length; int maxSum = MaxSumNoAdjacent(arr, n); Console.WriteLine(maxSum); }} |
Javascript
function maxSumNoAdjacent(arr, n) { if (n === 0) return 0; if (n === 1) return arr[0]; let include = arr[0]; let exclude = 0; for (let i = 1; i < n; i++) { let prevInclude = include; include = exclude + arr[i]; exclude = Math.max(prevInclude, exclude); } return Math.max(include, exclude);}let arr = [12, 9, 7, 33];let n = arr.length;let maxSum = maxSumNoAdjacent(arr, n);console.log(maxSum); |
PHP
<?phpfunction maxSumNoAdjacent($arr, $n) { if ($n == 0) return 0; if ($n == 1) return $arr[0]; $include = $arr[0]; $exclude = 0; for ($i = 1; $i < $n; $i++) { $prevInclude = $include; $include = $exclude + $arr[$i]; $exclude = max($prevInclude, $exclude); } return max($include, $exclude);}$arr = [12, 9, 7, 33];$n = count($arr);$maxSum = maxSumNoAdjacent($arr, $n);echo $maxSum . "\n";?> |
Output
45
Time Complexity :O(n), where n is the size of the input array. This is because the code iterates through the array once in the for loop, performing a constant number of operations for each element.
Auxiliary Space : O(1), meaning it uses a constant amount of extra space. The space usage remains constant throughout the execution, regardless of the size of the input array. This is because the code only uses a few variables (include, exclude, prevInclude) to keep track of the maximum sum, and their space requirements do not depend on the size of the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
