• 0

Find maximum sum subarray (non-contiguous)
  • subarray
  • array
  • dynamicprogramming
  •   
    subscribe
  • Posted: 6 years ago
  • Edit
  • answers (1)
  • views (25544)

Suppose you are given an array of positive integers. Write an algorithm to find the maximum sum subarray such that no two elements are adjacent to each other in the input array.


Posted Answers

  • Posted: 6 years ago
  • 0 0
  • Edit

We can use dynamic programming to find the maximum sum subarray. The algorithm works as :


  • Create three integers - sum1, sum2 and sum3. sum1 and sum2 holds the current maximum sum inclusive and exclusive the current value respectively.
  • Initialize sum1 = first element of the array, sum2=0.
  • Put the maximum of sum1 and sum2 in sum3.Move the value of sum3 into sum2. Take the second element of the array and do the following : sum1=sum2+array[1].
  • Iterate through the array and repeat the last step for all the elements in the array.
  • Return the maximum of sum1 and sum2.

Time complexity = \( O(n) \).

public int maxsumNonContiguous(int[] array){
     /* Empty array */
     if(array == null)
        return 0;
        
     int arrayLength = array.length;
     /* Current maximum sum including the current value */
     int sum1 = array[0];
     /* Current maximum sum excluding the current value */
     int sum2 = 0;
     
     /* Iterate through the array from second element to the end */
     for(int i = 1; i  <  arrayLength; i++){
     
         /* Current maximum sum excluding the current index value */
         sum3 = Math.max(sum1,sum2);
         
         /* Move the value of sum3 into sum2 */
         sum2 = sum3;

         /* Current maximum sum including the current index value */
         sum1 = sum2 + array[i];
     }
     
     /* Return the maximum of sum1 and sum2 */
     return Math.max(sum1, sum2);
 }
You need to Sign In to post your solution.