Maximum Adjacent Sum of a Circular array

In this approach, the idea is to use recursion to optimally find the solution. At each element, we have two choices, either we choose that element or we don’t. Since this is a circular array so we need to take care of the case that when we are including the 0th element then we may or may not choose (‘N’ - 1)th element or when we don’t choose the 0th element then we need to choose the (‘N’ - 1)th element.

We can address this problem by first definitely including the 0th element and then recursively finding the minimum sum from the rest of the element and then we definitely include the (‘N’ - 1)th element and then recursively finding the minimum sum from the rest of the element. The minimum sum is given by the minimum of ( the value we got from  including the 0th, the value we got from including the  (‘N’ - 1)th element),

To recursively find the minimum sum we can make a recursive function, let the function be ‘F’, the function has two parameters, the index of the elements we are at and a flag value that denotes whether the last element was chosen or not.

If flag = 1 then (i.e, last value was not chosen)

F( idx, flag ) = ‘NUMS[ idx]’ + ‘F( idx+1, 0 ).

Else:

F( idx, flag) = min(  ‘NUMS[ idx]’ + ‘F( idx+1, 0 ), F( idx + 1, 1) ).

The steps are as follows:-

// Recursive function to get minimum sum.

Function getMinUtil( [ int ] nums, int idx, int flag):

1. If the value of 'IDX' is 'N' then return 0.
2. If the value of 'FLAG' is 1 choose the current element and recursively call the 'getMinUtil' function to choose the other elements. Return the sum of these values.
3. Else return the minimum value by either choosing the element or not choosing the element.

Function getMinCost( [ int ] nums):

1. Create an array 'EXCLUDE0' and assign all the values of 'NUMS' excluding value at 0.
2. Create an array 'EXCLUDEN' and assign all the values of 'NUMS' excluding value at 'N' - 1.
3. Initialize a variable 'ANS' with value of 'NUMS[ 0 ]' + the value returned by the recursive function 'getMinUtil' by passing the array 'EXCLUDE0' and ‘FLAG’ as 0 in the argument.
4. Update the value of 'ANS' with the minimum of 'ANS' and ( 'NUMS[ N - 1 ] + the value returned the recursive function 'getMinUtil' by passing the array 'EXCLUDEN' and ‘FLAG’ as 0 in the argument).
5. Return the value of 'ANS'.

In this approach, we will be optimizing the previous approach by storing the value of function ‘F’ for arguments (idx, flag) in a matrix, so that we don’t have to calculate the value of the function with the same arguments again and again.

The steps are as follows:-

// Recursive function to get minimum sum.

Function getMinUtil( [ int ] nums, int idx, int flag, [ [ int ] ] dp):

1. If the value of 'IDX' is 'N' then return 0.
2. If the value of 'DP[ idx ][ flag ]' != -1 then return its value.
3. If the value of 'FLAG' is 1 choose the current element and recursively call the 'getMinUtil' function to choose the other elements. Store the sum of these values and return it.
4. Else store the minimum value by either choosing the element or not choosing the element and then return it.

Function getMinCostl( [ int ] nums):

1. Create an array 'EXCLUDE0' and assign all the values of 'NUMS' excluding value at 0.
2. Create an array 'EXCLUDEN' and assign all the values of 'NUMS' excluding value at 'N' - 1.
3. Initialize an array of size 'N' x 2  'DP1' with value -1.
4. Initialize an array of size 'N' x 2  'DP2' with value -1.
5. Initialize a variable 'ANS' with value of 'NUMS[ 0 ]' + the value returned by the recursive function 'getMinUtil' by passing the array 'EXCLUDE0' and ‘DP1’ and flag as 0 in the argument.
6. Update the value of 'ANS' with the minimum of 'ANS' and ( 'NUMS[ N - 1 ] + the value returned the recursive function 'getMinUtil' by passing the array 'EXCLUDEN' and ‘DP2’ and flag as 0 in the argument).
7. Return the value of 'ANS'.

In this approach, We will find the minimum sum for each element and then use that minimum sum to get the value for the next element. For each element, we will calculate the value that we can get by including that element and the value without including that element.

The steps are as follows:-

// Iterative function to get minimum sum.

Function getMinUtil( [ int ] nums, int start, int end):

1. Initialize an array 'DP' of size 2 with value 0. ‘DP[ 0 ]’ denotes the minimum sum till ‘i’ if we do not include ‘i’th element and ‘DP[ 1 ]’ denotes the minimum sum till ‘i’ including that element.
2. Update the value of 'DP[ 1 ]' to 'NUMS[ start ]'.
3. Run a loop from 'i' = 'START' + 1 to 'END' - 1:
   • Initialize an array 'CUR' of size 2 with value 0.
   • If we do not include the current element then we have to include the previous element and hence, 'CUR[ 0 ]' = 'DP [ 1 ]'.
   • If we include the current element then we may or may not include the previous element and hence, 'CUR[ 1 ]' = 'NUMS[ i ]' + min( 'DP[ 0 ]', 'DP [ 1 ]').
   • Assign the values of 'CUR' to 'DP'.
4. Return the minimum of 'DP[ 0 ]' and 'DP[ 1 ]'.

Function getMinUtil( [ int ] nums, int idx, int flag):

1. Initialize a variable 'ANS' with value of 'NUMS[ 0 ]' + the value returned by the recursive function 'getMinUtil' by passing the array 'START' as 1 and  'END' as 'N'
2. Update the value of 'ANS' with the minimum of 'ANS' and ( 'NUMS[ N - 1 ] + the value returned by the recursive function 'getMinUtil' by passing 'START' as 1 and 'END' as 'N' - 1 in the argument).
3. Return the value of 'ANS'.