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

0 0 10 minutes read

Given an array arr[] 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 where the last and the first elements are assumed adjacent.
Examples:

Input: arr[] = {3, 5, 3}
Output: 5
Explanation:
We cannot take the first and last elements because they are considered to be adjacent, hence the output is 5.
Input arr[] = {1, 223, 41, 4, 414, 5, 16}
Output: 653
Explanation:
Taking elements form the index 1, 4 and 6 we get the maximum sum as 653.

Approach: The idea is to use the Memorization algorithm to solve the problem mentioned above. The most important observation is that the first and the last elements can never be chosen together. So, we can break the problem into two parts:

The maximum sum we can get from index 0 to the size of the array – 2
The maximum sum we can get from index 1 to size of the array – 1

The answer will be the maximum of these two sums which can be solved by using Dynamic Programming.
Below is the implementation of the above approach:

C++

// C++ program to find maximum sum
// in circular array such that
// no two elements are adjacent
 
#include <bits/stdc++.h>
using namespace std;
 
// Store the maximum possible at each index
vector<int> dp;
 
int maxSum(int i, vector<int>& subarr)
{
 
    // When i exceeds the index of the
    // last element simply return 0
    if (i >= subarr.size())
        return 0;
 
    // If the value has already been calculated,
    // directly return it from the dp array
    if (dp[i] != -1)
        return dp[i];
 
    // The next states are don't take
    // this element and go to (i + 1)th state
    // else take this element
    // and go to (i + 2)th state
    return dp[i]
           = max(maxSum(i + 1, subarr),
                 subarr[i]
                     + maxSum(i + 2, subarr));
}
 
// function to find the max value
int Func(vector<int> arr)
{
    vector<int> subarr = arr;
 
    // subarr contains elements
    // from 0 to arr.size() - 2
    subarr.pop_back();
 
    // Initializing all the values with -1
    dp.resize(subarr.size(), -1);
 
    // Calculating maximum possible
    // sum for first case
    int max1 = maxSum(0, subarr);
 
    subarr = arr;
 
    // subarr contains elements
    // from 1 to arr.size() - 1
    subarr.erase(subarr.begin());
 
    dp.clear();
 
    // Re-initializing all values with -1
    dp.resize(subarr.size(), -1);
 
    // Calculating maximum possible
    // sum for second case
    int max2 = maxSum(0, subarr);
 
    // Printing the maximum between them
    cout << max(max1, max2) << endl;
}
 
// Driver code
int main()
{
 
    vector<int> arr = { 1, 2, 3, 1 };
 
    Func(arr);
 
    return 0;
}

Java

// Java program to find maximum sum
// in circular array such that
// no two elements are adjacent
import java.util.*;
class GFG{
 
// Store the maximum 
// possible at each index
static Vector<Integer> dp = 
              new Vector<>();
 
static int maxSum(int i, 
                  Vector<Integer> subarr)
{
  // When i exceeds the index of the
  // last element simply return 0
  if (i >= subarr.size())
    return 0;
 
  // If the value has already 
  // been calculated, directly 
  // return it from the dp array
  if (dp.get(i) != -1)
    return dp.get(i);
 
  // The next states are don't take
  // this element and go to (i + 1)th state
  // else take this element
  // and go to (i + 2)th state
  dp.add(i, Math.max(maxSum(i + 1, subarr),
                     subarr.get(i) + 
                     maxSum(i + 2, subarr)));
  return dp.get(i);
}
 
// function to find the max value
static void Func(Vector<Integer> arr)
{
  Vector<Integer> subarr = 
         new Vector<>();
  subarr.addAll(arr);
 
  // subarr contains elements
  // from 0 to arr.size() - 2
  subarr.remove(subarr.size() - 1);
 
  // Initializing all the values with -1
  dp.setSize(subarr.size());
  Collections.fill(dp, -1);
 
  // Calculating maximum possible
  // sum for first case
  int max1 = maxSum(0, subarr);
 
  subarr = arr;
 
  // subarr contains elements
  // from 1 to arr.size() - 1
  subarr.remove(0);
 
  dp.clear();
 
  // Re-initializing all values with -1
  dp.setSize(subarr.size());
  Collections.fill(dp, -1);
 
 
  // Calculating maximum possible
  // sum for second case
  int max2 = maxSum(0, subarr);
 
  // Printing the maximum between them
  System.out.print(Math.max(max1, max2) + "\n");
}
 
// Driver code
public static void main(String[] args)
{
  Vector<Integer> arr =new Vector<>();
  arr.add(1);
  arr.add(2);
  arr.add(3);
  arr.add(1);
  Func(arr);
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program to find maximum sum
# in circular array such that
# no two elements are adjacent
 
# Store the maximum possible at each index
dp = []
 
def maxSum(i, subarr):
 
    # When i exceeds the index of the
    # last element simply return 0
    if (i >= len(subarr)):
        return 0
 
    # If the value has already been 
    # calculated, directly return 
    # it from the dp array
    if (dp[i] != -1):
        return dp[i]
 
    # The next states are don't take
    # this element and go to (i + 1)th state
    # else take this element
    # and go to (i + 2)th state
    dp[i] = max(maxSum(i + 1, subarr), 
                subarr[i] +
                maxSum(i + 2, subarr))
    return dp[i]
 
# function to find the max value
def Func(arr):
    subarr = arr
 
    # subarr contains elements
    # from 0 to arr.size() - 2
    subarr.pop()
    global dp
     
    # Initializing all the values with -1
    dp= [-1] * (len(subarr))
 
    # Calculating maximum possible
    # sum for first case
    max1 = maxSum(0, subarr)
 
    subarr = arr
 
    # subarr contains elements
    # from 1 to arr.size() - 1
    subarr = subarr[:]
 
    del dp
 
    # Re-initializing all values with -1
    dp = [-1] * (len(subarr))
 
    # Calculating maximum possible
    # sum for second case
    max2 = maxSum(0, subarr)
 
    # Printing the maximum between them
    print(max(max1, max2))
 
# Driver code
if __name__ == "__main__":
    arr = [1, 2, 3, 1]
    Func(arr)
     
# This code is contributed by Chitranayal

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Store the maximum 
  // possible at each index
  static List<int> dp = new List<int>();
 
  static int maxSum(int i, List<int> subarr)
  {
     
    // When i exceeds the index of the
    // last element simply return 0
    if (i >= subarr.Count)
      return 0;
 
    // If the value has already 
    // been calculated, directly 
    // return it from the dp array
    if (dp[i] != -1)
      return dp[i];
 
    // The next states are don't take
    // this element and go to (i + 1)th state
    // else take this element
    // and go to (i + 2)th state
    dp[i] = Math.Max(maxSum(i + 1, subarr), subarr[i] + maxSum(i + 2, subarr));
    return dp[i];
  }
 
  // function to find the max value
  static void Func(List<int> arr)
  {
    List<int> subarr = new List<int>(arr);
 
    // subarr contains elements
    // from 0 to arr.size() - 2
    subarr.RemoveAt(subarr.Count - 1);
 
    // Initializing all the values with -1
    for(int i = 0 ; i < subarr.Count ; i++){
      dp.Add(-1);
    }
 
    // Calculating maximum possible
    // sum for first case
    int max1 = maxSum(0, subarr);
 
    subarr = arr;
 
    // subarr contains elements
    // from 1 to arr.size() - 1
    subarr.RemoveAt(0);
 
    dp.Clear();
 
    // Re-initializing all values with -1
    for(int i = 0 ; i < subarr.Count ; i++){
      dp.Add(-1);
    }
 
 
    // Calculating maximum possible
    // sum for second case
    int max2 = maxSum(0, subarr);
 
    // Printing the maximum between them
    Console.WriteLine(Math.Max(max1, max2));
  }
 
  // Driver code
  public static void Main(string[] args){
 
    List<int> arr =new List<int>();
    arr.Add(1);
    arr.Add(2);
    arr.Add(3);
    arr.Add(1);
    Func(arr);
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
// Javascript program to find maximum sum
// in circular array such that
// no two elements are adjacent
 
// Store the maximum
// possible at each index
let dp =[];
function  maxSum(i,subarr)
{
    // When i exceeds the index of the
  // last element simply return 0
  if (i >= subarr.length)
    return 0;
  
  // If the value has already
  // been calculated, directly
  // return it from the dp array
  if (dp[i] != -1)
    return dp[i];
  
  // The next states are don't take
  // this element and go to (i + 1)th state
  // else take this element
  // and go to (i + 2)th state
  dp[i] = Math.max(maxSum(i + 1, subarr),
                     subarr[i] +
                     maxSum(i + 2, subarr));
  return dp[i];
}
 
// function to find the max value
function Func(arr)
{
    let subarr =arr;
  
  // subarr contains elements
  // from 0 to arr.size() - 2
  subarr.pop();
  
  // Initializing all the values with -1
  dp=new Array(subarr.length);
  for(let i=0;i<subarr.length;i++)
  {
      dp[i]=-1;
  }
  
  // Calculating maximum possible
  // sum for first case
  let max1 = maxSum(0, subarr);
  
  subarr = arr;
  
  // subarr contains elements
  // from 1 to arr.size() - 1
  subarr.shift();
  
  dp=[];
  
  // Re-initializing all values with -1
  dp=new Array(subarr.length);
  for(let i=0;i<dp.length;i++)
  {
      dp[i]=-1;
  }
  
  
  // Calculating maximum possible
  // sum for second case
  let max2 = maxSum(0, subarr);
  
  // Printing the maximum between them
  document.write(Math.max(max1, max2) + "<br>");
}
 
// Driver code
 
let arr=[1,2,3,1];
  Func(arr);
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

Time Complexity: O(N)
Auxiliary Space Complexity: O(N)

Method 2: Tabulation

C++

// C++ program to find maximum sum
// in circular array such that
// no two elements are adjacent
 
#include <bits/stdc++.h>
using namespace std;
 
 
int findMax(vector<int> arr, int n, vector<int> &dp){
    dp[0] = arr[0] ;
 
    for(int i = 1 ; i <= n ; i++ ){
      int pick  = arr[i];
      if(i > 1){
        pick += dp[i-2] ;
      }
 
      int notPick = 0 + dp[i-1] ;
      dp[i] = max(pick, notPick) ;
    }
 
    return dp[n] ;
}
 
// function to find the max value
int Func(vector<int> nums)
{
    if(nums.size() == 1){
        return nums[0] ;
    }
    // First and last element together
    // can never be in the answer
    vector<int> v1, v2 ;
    int n = nums.size() ;
    // Store the maximum possible at each index
    vector<int> dp(nums.size() , -1) ;
 
    for(int i = 0 ; i < n ; i++ ){
      if(i != 0) v1.push_back(nums[i] ) ;
      if(i != n-1) v2.push_back(nums[i] ) ;
    }
     
    // calculate the max when
    // first element was considered
     // and when last element was considered
    cout<< max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)) ;
}
 
// Driver code
int main()
{
 
    vector<int> arr = { 1, 2, 3, 1 };
 
    Func(arr);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
class GFG {
 
  static int findMax(List<Integer> arr, int n, int []dp){
    dp[0] = arr.get(0) ;
 
    for(int i = 1 ; i <= n ; i++ ){
      int pick  = arr.get(i);
      if(i > 1){
        pick += dp[i-2] ;
      }
 
      int notPick = 0 + dp[i-1] ;
      dp[i] = Math.max(pick, notPick) ;
    }
 
    return dp[n] ;
  }
 
  // function to find the max value
  static int Func(int[] nums)
  {
    if(nums.length == 1){
      return nums[0];
    }
    // First and last element together
    // can never be in the answer
    List<Integer> v1 = new ArrayList<>();
    List<Integer> v2 = new ArrayList<>();
 
    int n = nums.length ;
    // Store the maximum possible at each index
    int dp[] = new int[nums.length];
 
    Arrays.fill(dp,-1);
 
    for(int i = 0 ; i < n ; i++ ){
      if(i != 0) v1.add(nums[i] ) ;
      if(i != n-1) v2.add(nums[i] ) ;
    }
 
    // calculate the max when
    // first element was considered
    // and when last element was considered
    System.out.println(Math.max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)));
 
    return 0;
  }
 
  public static void main (String[] args) {
 
    int[] arr = { 1, 2, 3, 1 };
    Func(arr);
  }
}
 
// This code is contributed by aadityaburujwale.

Python3

# Python program implementation
 
def findMax(arr, n, dp):
    dp[0] = arr[0] 
 
    for i in range(1,n+1):
        pick = arr[i]
        if(i > 1):
            pick += dp[i-2]
 
        notPick = 0 + dp[i-1]
        dp[i] = max(pick, notPick)
 
    return dp[n]
 
# function to find the max value
def Func(nums):
 
    if(len(nums) == 1):
        return nums[0]
 
    # First and last element together
    # can never be in the answer
    v1 = []
    v2 = []
    n = len(nums)
     
    # Store the maximum possible at each index
    dp = [-1 for i in range(len(nums))]
 
    for i in range(n):
        if(i != 0):
            v1.append(nums[i])
        if(i != n-1):
            v2.append(nums[i])
 
    # calculate the max when
    # first element was considered
    # and when last element was considered
    print(max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)))
 
# Driver code
arr = [ 1, 2, 3, 1 ]
Func(arr)
 
# This code is contributed by shinjanpatra

C#

// C# program to find maximum sum
// in circular array such that
// no two elements are adjacent
using System;
using System.Collections.Generic;
 
public class HelloWorld
{
 
  public static int findMax(List<int> arr, int n, List<int> dp){
    dp[0] = arr[0] ;
 
    for(int i = 1 ; i <= n ; i++ ){
      int pick = arr[i];
      if(i > 1){
        pick += dp[i-2] ;
      }
 
      int notPick = 0 + dp[i-1] ;
      dp[i] = Math.Max(pick, notPick) ;
    }
 
    return dp[n] ;
  }
 
  // function to find the max value
  public static int Func(List<int> nums)
  {
    if(nums.Count == 1){
      return nums[0] ;
    }
    // First and last element together
    // can never be in the answer
    List<int> v1 = new List<int>();
    List<int> v2 = new List<int>();
    int n = nums.Count ;
    // Store the maximum possible at each index
    List<int> dp = new List<int>();
 
    for(int i =0;i<nums.Count;i++)
    {
      dp.Add(-1);
    }
 
    for(int i = 0 ; i < n ; i++ ){
      if(i != 0) v1.Add(nums[i] ) ;
      if(i != n-1) v2.Add(nums[i] ) ;
    }
 
    // calculate the max when
    // first element was considered
    // and when last element was considered
    return Math.Max(findMax(v1, n-2, dp),findMax(v2, n-2, dp));
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    List<int> arr = new List<int>();
    arr.Add(1);
    arr.Add(2);
    arr.Add(3);
    arr.Add(1);
 
    Console.WriteLine(Func(arr));
 
  }
}
 
// This code is contributed by aadityamaharshi21.

Javascript

<script>
 
// JavaScript program to implement above approach
function findMax(arr, n, dp)
{
    dp[0] = arr[0] ;
 
    for(let i = 1 ; i <= n ; i++ )
    {
        let pick = arr[i];
        if(i > 1)
        {
            pick += dp[i-2] ;
        }
 
        let notPick = 0 + dp[i-1] ;
        dp[i] = Math.max(pick, notPick) ;
    }
 
    return dp[n];
}
 
// function to find the max value
function Func(nums)
{
    if(nums.length == 1){
        return nums[0] ;
    }
     
    // First and last element together
    // can never be in the answer
    let v1 = [], v2 = [];
    let n = nums.length ;
     
    // Store the maximum possible at each index
    let dp = new Array(nums.length).fill(-1) ;
 
    for(let i = 0 ; i <br n ; i++ ){
        if(i != 0) v1.push(nums[i]) ;
        if(i != n-1) v2.push(nums[i]) ;
    }
     
    // calculate the max when
    // first element was considered
    // and when last element was considered
    document.write(Math.max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)),"</br>");
}
 
// Driver code
let arr = [ 1, 2, 3, 1 ];
Func(arr);
 
// This code is contributed by shinjanpatra
 
</script>

Output

Time Complexity: O(N)

Auxiliary Space Complexity: O(N)

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 zambiatek!