Maximum sum such that no two elements are adjacent | Set 2

19 June 2025

0

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 10
using namespace std;
 
// variable to store states of dp
int dp[maxLen];
 
// variable to check if a given state
// has been solved
bool v[maxLen];
 
// Function to find the maximum sum subsequence
// such that no two elements are adjacent
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] = 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 code
int 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 approach
maxLen = 10
 
# variable to store states of dp
dp = [0 for i in range(maxLen)]
 
# variable to check if a given state 
# has been solved
v = [0 for i in range(maxLen)]
 
# Function to find the maximum sum subsequence
# such that no two elements are adjacent
def 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 code
if __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 approach
var maxLen = 10;
 
// variable to store states of dp
var dp = Array(maxLen);
 
// variable to check if a given state
// has been solved
var v = Array(maxLen);
 
// 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 (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 code
var 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

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 adjacent
int 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 code
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 {
    // 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 adjacent
function 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 code
const arr = [12, 9, 7, 33];
console.log(maxSum(arr));

Output

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";
?>

Output

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!

Maximum sum such that no two elements are adjacent | Set 2

C++

Java

Python3

C#

Javascript

PHP

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

PHP

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US