Array Dynamic Programming Tabulation
Intermediate Level

Implement the maximumNonAdjacentSum method that finds the maximum sum using values that are not adjacent.

The input contains an integer array nums and its length size. Your task is to select numbers from the array so that no two selected numbers are adjacent.

Return the maximum possible sum of the selected numbers. For example, in [2,7,9,3,1], selecting 2 + 9 + 1 gives 12, which is the maximum valid non-adjacent sum.

Example 1
Input:
nums (int[]) = [2,7,9,3,1]
size (int) = 5
Return:
(int) 12
Example 2
Input:
nums (int[]) = [5,1,1,5]
size (int) = 4
Return:
(int) 10
Example 3
Input:
nums (int[]) = [4]
size (int) = 1
Return:
(int) 4

At each index, there are two choices: take the current number or skip it.

If you take the current number, you must add it to the best sum available before the previous index. If you skip it, the best sum remains the same as the previous index.

Keep two values: one for the best sum up to the previous position and one for the best sum before that. This avoids using an extra array.

Pseudocode:

function maximumNonAdjacentSum(nums, size):
    includePrevious = 0
    excludePrevious = 0
    for i from 0 to size - 1:
        takeCurrent = excludePrevious + nums[i]
        skipCurrent = includePrevious
        currentBest = max(takeCurrent, skipCurrent)
        excludePrevious = includePrevious
        includePrevious = currentBest
    return includePrevious
Run your code to see the result.