Print maximum sum when no two elements are adjacent

Share

Problem: For a given array of positive integers, obtain maximum sum of elements such that no two elements are adjacent.

Problem Explanation: For a given array a ={5, 8, 10, 18, 1, 9},  the maximum sum is obtained from elements 8, 18 and 9. Hence maximum sum is 35.

Java Implementation

public int maxArraySum(int arr[]) {
    int sumOdd = 0, sumEven = 0;

    for (int i = 0; i < arr.length; i++) {
        if (i % 2 == 0) {
            sumEven += arr[i];
        } else {
            sumOdd += arr[i];
        }
    }

    return (sumEven > sumOdd ? sumEven : sumOdd);
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)