mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
35 lines
636 B
Go
35 lines
636 B
Go
package leetcode
|
||
|
||
func rob213(nums []int) int {
|
||
n := len(nums)
|
||
if n == 0 {
|
||
return 0
|
||
}
|
||
if n == 1 {
|
||
return nums[0]
|
||
}
|
||
if n == 2 {
|
||
return max(nums[0], nums[1])
|
||
}
|
||
// 由于首尾是相邻的，所以需要对比 [0，n-1]、[1，n] 这两个区间的最大值
|
||
return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1))
|
||
}
|
||
|
||
func rob213_1(nums []int, start, end int) int {
|
||
preMax := nums[start]
|
||
curMax := max(preMax, nums[start+1])
|
||
for i := start + 2; i <= end; i++ {
|
||
tmp := curMax
|
||
curMax = max(curMax, nums[i]+preMax)
|
||
preMax = tmp
|
||
}
|
||
return curMax
|
||
}
|
||
|
||
func max(a int, b int) int {
|
||
if a > b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|