[数据结构与算法]动态规划③

①

152. 乘积最大子数组

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

示例 1:

输入: [2,3,-2,4]
输出: 6
解释:?子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释:?结果不能为 2, 因为 [-2,-1] 不是子数组。

# 考虑负数情况，需要一个数组来保存最小值
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
       

        dpmax=[0 for _ in range(len(nums))]
        dpmin=[0 for _ in range(len(nums))]
     
        dpmax[0]=nums[0]
        dpmin[0]=nums[0]


        for i in range(1,len(nums)):
            dpmax[i]=max(nums[i],dpmax[i-1]*nums[i],dpmin[i-1]*nums[i])
            dpmin[i]=min(nums[i],dpmin[i-1]*nums[i],dpmax[i-1]*nums[i])
        # return max(max(dpmax),min(dpmin)) 
        return max(dpmax)  

②

1567. 乘积为正数的最长子数组长度

给你一个整数数组?nums?，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

示例? 1：

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

示例 2：

输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

示例 3：

输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dpmax=[0]*len(nums)   #正数乘积个数
        dpmin=[0]*len(nums)   #负数乘积个数

        if nums[0]>0:
            dpmax[0]=1
        if nums[0]<0:
            dpmin[0]=1

        for i in range(1,len(nums)):
            if nums[i]>0:
                dpmax[i]=dpmax[i-1]+1
                dpmin[i]=(dpmin[i-1]+1 if dpmin[i-1]>0 else 0 )
            elif nums[i]<0:
                dpmax[i]=(dpmin[i-1]+1 if dpmin[i-1]>0 else 0)
                dpmin[i]=dpmax[i-1]+1
            else:
                dpmin[i]=dpmax[i]=0
        return max(dpmax)

③

1014. 最佳观光组合

给你一个正整数数组?values，其中?values[i]?表示第?i?个观光景点的评分，并且两个景点?i?和?j?之间的?距离?为?j - i。

一对景点（i < j）组成的观光组合的得分为?values[i] + values[j] + i - j?，也就是景点的评分之和?减去?它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
       
        # alist=[]
        # dp=[[0]*len(values) for _ in range(len(values)) ]
        
        # for i in range(len(values)):
        #     for j in range(i+1,len(values)):
        #         dp[i][j]=values[i]+values[j]+i-j
        #     alist.append(max(dp[i]))
        # return max(alist)
        maxl=0
        tmp=values[0]+0
        for j in range(1,len(values)):
            maxl=max(maxl,tmp+values[j]-j)
            tmp=max(tmp,values[j]+j)
        return maxl

④

121. 买卖股票的最佳时机

给定一个数组?prices?，它的第?i?个元素?prices[i]?表示一支给定股票第?i?天的价格。

你只能选择?某一天?买入这只股票，并选择在?未来的某一个不同的日子?卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回?0?。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        m=prices[0]
        dp=[0] *len(prices)
        for i in range(1,len(prices)):
            if prices[i]<m:
                m=prices[i]

            dp[i]=max(dp[i-1],prices[i]-m)
        return max(dp)
        

⑤

122. 买卖股票的最佳时机 II

难度简单1279

给定一个数组?prices?，其中?prices[i]?是一支给定股票第?i?天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
?    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
?    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例?3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        profit=0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                profit+=prices[i]-prices[i-1]
        return profit