Maximum sum such that no two elements are adjacent

Recently I came accross an interesting computer science problem.  The problem goes like this:

You are given an array of integers e.g. { 5, 5,  10, 100, 10, 5} you need to find maximum sum which can be achieved using non adjecent elements. In this example maximum sum is 110 which is acheived by including elements { 5, 100, 5 }. We will start with finding maximum sum and later extend it to find elements contributing to maximum sum.

The idea is to calculate maximum sum which can be achived using elements till i and store it in dp[i] . Now for next element i+1 we can include it or exclude it. If we include arr[i+1] then we need to exclude arr[i] so max sum including arr[i+1] can be dp[i-1]+arr[i+1] and maximum sum which can be achived excluding arr[i+1] will be dp[i] so dp[i+1]= max(dp[i-1]+arr[i+1], dp[i]) .  The code for this solution is given below.

public class MaxNonAdjSum1 {
	
    int FindMaxSum(int arr[], int n)
    {
    	int[] dp = new int[n];
    	
    	if(arr[0]>0) {
    		dp[0] = arr[0];
    	} else {
    		dp[0]= 0;
    	}
 
        for (int i = 1; i < n; i++)
        {
        	if((i>=2?dp[i-2]:0)+arr[i]>dp[i-1]) {
        		dp[i]= (i>=2?dp[i-2]:0)+arr[i];
        	} else {
        		dp[i] = dp[i-1];
        	}
        }
        return dp[n-1];
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
    	MaxNonAdjSum1 sum = new MaxNonAdjSum1();
        int arr[] = new int[]{5, 5, 10, 100, 10, 5};
        System.out.println(sum.FindMaxSum(arr, arr.length));
    }

}

In the above code we are using dp[i], dp[i-1] and dp[i-2] only inside the loop. We can replace them with three variables and we can avoid allocating array dp which will reduce space complexity from O(N) to O(1).

But for now let us concentrate on getting elements who are contributing to maximum sum. The idea it to keep a boolean array to keep track if it is included in max sum. If we include arr[i] then arr[i-1] will have to be excluded. So when we set incFlag[i]=true then we set incFlag[i-1]=false. The code for this solution is provided below.

import java.util.ArrayList;

public class MaxNonAdjSum {
	
    ArrayList<Integer> FindMaxSum(int arr[], int n)
    {
    	boolean[] incFlag = new boolean[n];
    	int[] dp = new int[n];
    	
    	if(arr[0]>0) {
    		dp[0] = arr[0];
    		incFlag[0] = true;
    	} else {
    		dp[0]= 0;
    		incFlag[0] = false;
    	}
 
        for (int i = 1; i < n; i++)
        {
        	
        	if((i>=2?dp[i-2]:0)+arr[i]>dp[i-1]) {
        		incFlag[i-1] = false;
        		dp[i]= (i>=2?dp[i-2]:0)+arr[i];
        		incFlag[i] = true;
        	} else {
        		dp[i] = dp[i-1];
        	}
        }
 
        ArrayList<Integer> result = new ArrayList<>();
        for(int i=0; i<n; i++) {
        	if(incFlag[i]) {
        		result.add(arr[i]);
        	}
        }
        return result;
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
    	MaxNonAdjSum sum = new MaxNonAdjSum();
        int arr[] = new int[]{5, 5, 10, 100, 10, 5};
        System.out.println(sum.FindMaxSum(arr, arr.length));
    }

}

One optimization which is still left is to replace dp[i-2], dp[i-1] and dp[i] with three variables and shift there values in every iteration. This will reduce space complexity from O(N) to O(1).