LeetCode 不相邻最大和题解

LeetCode 不相邻最大和题解

题目描述

给定一个数组，计算不相邻元素的最大和。

示例：

输入：nums = [1, 2, 3, 1]
输出：4

解题思路

方法：动态规划

思路：

• 使用动态规划，dp[i] 表示考虑前 i 个元素能获得的最大和。
• dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码实现

def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] prev2 = 0 prev1 = nums[0] for i in range(1, len(nums)): curr = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = curr return prev1 # 测试 def test_rob(): nums = [1, 2, 3, 1] print(rob(nums)) # 输出：4 if __name__ == "__main__": test_rob()

总结

不相邻最大和是动态规划的典型应用，通过维护前两个状态来计算最大和。