力扣刷题 day41：10-11

1.乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

方法一：动态规划 

#方法一：动态规划
def maxProduct(nums):
    dp_max=[1 for i in range(len(nums)+1)] #dp[i]表示以i位置结尾的数组的乘积最大值
    dp_min=[1 for i in range(len(nums) +1)] #dp[i]表示i位置结尾数组的乘积最小值
    ans=float('-inf')
    for i in range(1,len(nums)+1):
        dp_max[i]=max(dp_max[i-1]*nums[i-1],dp_min[i-1]*nums[i-1],nums[i-1]) #要么最大值*正数，要么可能最小值*负数，要么就取这一个数
        dp_min[i]=min(dp_max[i-1]*nums[i-1],dp_min[i-1]*nums[i-1],nums[i-1])
        if dp_max[i]>ans:
            ans=dp_max[i]
    return ans

2.打家劫舍 

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

方法一：动态规划 

#方法一：动态规划
def rob(nums):
    dp=[0 for i in range(len(nums)+1)] #dp[i]表示i之前的最大金额数目
    for i in range(len(nums)):
            if i>0:
                dp[i+1]=max(dp[i],dp[i-1]+nums[i]) #要么等于前一个位置的最大金额数目，要么加上当前位置的值
            else:
                 dp[i+1]=max(nums[i],dp[i]) #边界位置
    return dp[-1]

3.打家劫舍 II 

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

方法一：动态规划 

#方法一：动态规划
def rob(nums):
    if len(nums) == 1:
        return nums[0] #特殊情况
    def my_rob(nums):
        cur,pre=0,0 #当前最大金额数，上一个位置的最大金额数
        for i in nums:
            cur,pre=max(pre+i,cur),cur #要么前一个位置的，要么前两个位置的+现在的
        return cur
    return max(my_rob(nums[:len(nums)-1]),my_rob(nums[1:]))  #要么包含第一个位置，要么不包含