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) =
5Returns (int)
12Example 2
Input
nums (int[]) =
[5,1,1,5]size (int) =
4Returns (int)
10Example 3
Input
nums (int[]) =
[4]size (int) =
1Returns (int)
4At 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 includePreviousReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run