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).
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++
#include <bits/stdc++.h>
#define maxLen 10
using namespace std;
int dp[maxLen];
bool v[maxLen];
int maxSum( int arr[], int i, int n)
{
if (i >= n)
return 0;
if (v[i])
return dp[i];
v[i] = 1;
dp[i] = max(maxSum(arr, i + 1, n),
arr[i] + maxSum(arr, i + 2, n));
return dp[i];
}
int main()
{
int arr[] = { 12, 9, 7, 33 };
int n = sizeof (arr) / sizeof ( int );
cout << maxSum(arr, 0, n);
return 0;
}
|
Java
class GFG
{
static int maxLen = 10 ;
static int dp[] = new int [maxLen];
static boolean v[] = new boolean [maxLen];
static int maxSum( int arr[], int i, int n)
{
if (i >= n)
return 0 ;
if (v[i])
return dp[i];
v[i] = true ;
dp[i] = Math.max(maxSum(arr, i + 1 , n),
arr[i] + maxSum(arr, i + 2 , n));
return dp[i];
}
public static void main(String args[])
{
int arr[] = { 12 , 9 , 7 , 33 };
int n = arr.length;
System.out.println( maxSum(arr, 0 , n));
}
}
|
Python3
maxLen = 10
dp = [ 0 for i in range (maxLen)]
v = [ 0 for i in range (maxLen)]
def maxSum(arr, i, n):
if (i > = n):
return 0
if (v[i]):
return dp[i]
v[i] = 1
dp[i] = max (maxSum(arr, i + 1 , n),
arr[i] + maxSum(arr, i + 2 , n))
return dp[i]
if __name__ = = '__main__' :
arr = [ 12 , 9 , 7 , 33 ]
n = len (arr)
print (maxSum(arr, 0 , n))
|
C#
using System;
class GFG
{
static int maxLen = 10;
static int [] dp = new int [maxLen];
static bool [] v = new bool [maxLen];
static int maxSum( int [] arr, int i, int n)
{
if (i >= n)
return 0;
if (v[i])
return dp[i];
v[i] = true ;
dp[i] = Math.Max(maxSum(arr, i + 1, n),
arr[i] + maxSum(arr, i + 2, n));
return dp[i];
}
public static void Main()
{
int [] arr = { 12, 9, 7, 33 };
int n = arr.Length;
Console.Write( maxSum(arr, 0, n));
}
}
|
Javascript
<script>
var maxLen = 10;
var dp = Array(maxLen);
var v = Array(maxLen);
function maxSum(arr, i, n)
{
if (i >= n)
return 0;
if (v[i])
return dp[i];
v[i] = 1;
dp[i] = Math.max(maxSum(arr, i + 1, n),
arr[i] + maxSum(arr, i + 2, n));
return dp[i];
}
var arr = [12, 9, 7, 33 ];
var n = arr.length;
document.write( maxSum(arr, 0, n));
</script>
|
PHP
<?php
$maxLen = 10;
$dp = array_fill (0, $GLOBALS [ 'maxLen' ], 0);
$v = array_fill (0, $GLOBALS [ 'maxLen' ], 0);
function maxSum( $arr , $i , $n )
{
if ( $i >= $n )
return 0;
if ( $GLOBALS [ 'v' ][ $i ])
return $GLOBALS [ 'dp' ][ $i ];
$GLOBALS [ 'v' ][ $i ] = 1;
$GLOBALS [ 'dp' ][ $i ] = max(maxSum( $arr , $i + 1, $n ),
$arr [ $i ] + maxSum( $arr , $i + 2, $n ));
return $GLOBALS [ 'dp' ][ $i ];
}
$arr = array ( 12, 9, 7, 33 );
$n = count ( $arr );
echo maxSum( $arr , 0, $n );
?>
|
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].
C++
#include <bits/stdc++.h>
using namespace std;
int maxSum( int arr[], int n)
{
if (n == 0)
return 0;
if (n == 1)
return arr[0];
if (n == 2)
return max(arr[0], arr[1]);
int dp[n];
dp[0] = arr[0];
dp[1] = max(arr[0], arr[1]);
for ( int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]);
}
return dp[n - 1];
}
int 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 {
public static int maxSum( int [] arr, int n)
{
if (n == 0 )
return 0 ;
if (n == 1 )
return arr[ 0 ];
if (n == 2 )
return Math.max(arr[ 0 ], arr[ 1 ]);
int [] dp = new int [n];
dp[ 0 ] = arr[ 0 ];
dp[ 1 ] = Math.max(arr[ 0 ], arr[ 1 ]);
for ( int i = 2 ; i < n; i++) {
dp[i] = Math.max(dp[i - 1 ], arr[i] + dp[i - 2 ]);
}
return dp[n - 1 ];
}
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):
if n = = 0 :
return 0
if n = = 1 :
return arr[ 0 ]
if n = = 2 :
return max (arr[ 0 ], arr[ 1 ])
dp = [ 0 ] * n
dp[ 0 ] = arr[ 0 ]
dp[ 1 ] = max (arr[ 0 ], arr[ 1 ])
for i in range ( 2 , n):
dp[i] = max (dp[i - 1 ], arr[i] + dp[i - 2 ])
return dp[n - 1 ]
arr = [ 12 , 9 , 7 , 33 ]
n = len (arr)
print (maxSum(arr, n))
|
C#
using System;
class GFG {
static int maxSum( int [] arr, int n)
{
if (n == 0)
return 0;
if (n == 1)
return arr[0];
if (n == 2)
return Math.Max(arr[0], arr[1]);
int [] dp = new int [n];
dp[0] = arr[0];
dp[1] = Math.Max(arr[0], arr[1]);
for ( int i = 2; i < n; i++) {
dp[i] = Math.Max(dp[i - 1], arr[i] + dp[i - 2]);
}
return dp[n - 1];
}
static void Main()
{
int [] arr = { 12, 9, 7, 33 };
int n = arr.Length;
Console.WriteLine(maxSum(arr, n));
}
}
|
Javascript
function maxSum(arr) {
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]);
const dp = new Array(n);
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
}
return dp[n - 1];
}
const arr = [12, 9, 7, 33];
console.log(maxSum(arr));
|
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
<?php
function 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" ;
?>
|
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.