hardDynamic Programming 1DPure DSA~30 min
Maximum Non-Adjacent Sum on a Circular Street
Houses are arranged in a circle, so the first and last are adjacent. You cannot pick two adjacent houses. Maximize the total value collected.
Problem
Given an integer array nums where nums[i] is the value at house i and houses form a circle (house 0 is adjacent to house n-1), return the maximum sum obtainable without choosing two adjacent houses.
Input
An integer array nums of house values arranged circularly.
Output
An integer: the maximum non-adjacent circular sum.
Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
- Houses 0 and n-1 are adjacent.
Examples
Example 1
Input
nums = [2,3,2]
Output
3
You cannot take both house 0 and house 2; the best single choice is 3.
Example 2
Input
nums = [1,2,3,1]
Output
4
Take houses 0 and 2 (1 + 3 = 4).