Question

link

There is an integer array consisting positive numbers only.

Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.

Solution

It’s a little tricky to write the equation. Always remember the basic principle of DP is to assume that solution is found for (i -1), and then we calculate solution for input (i).

Don’t miss the (i-1) part.

Code

written by me

public int maxSumNonConsec(int[] input) {
    int len = input.length;
    int[] dp = new int[len];
    dp[0] = input[0];
    dp[1] = Math.max(input[0], input[1]);
    for (int i = 2; i < len; i++) {
        dp[i] = Math.max(dp[i - 1], input[i] + dp[i - 2]);
    }
    return dp[len - 1];
}