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 indexvector<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 valueint 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 codeint 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 adjacentimport java.util.*;class GFG{// Store the maximum // possible at each indexstatic 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 valuestatic 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 codepublic 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 indexdp = []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 valuedef 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 codeif __name__ == "__main__": arr = [1, 2, 3, 1] Func(arr) # This code is contributed by Chitranayal |
C#
// C# program to implement above approachusing 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 indexlet 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 valuefunction 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 codelet arr=[1,2,3,1]; Func(arr);// This code is contributed by avanitrachhadiya2155</script> |
Output
4
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 valueint 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 codeint 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 implementationdef 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 valuedef 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 codearr = [ 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 adjacentusing 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 approachfunction 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 valuefunction 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 codelet arr = [ 1, 2, 3, 1 ];Func(arr);// This code is contributed by shinjanpatra</script> |
Output
4
Time Complexity: O(N)
Auxiliary Space Complexity: O(N)
Similar article: Maximum sum in circular array such that no two elements are adjacent
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!
