最大非降子序列最大子序和买卖股票的最佳时间1python

118 阅读 0 评论 78 点赞

我是靠谱客的博主洁净手套，最近开发中收集的这篇文章主要介绍最大非降子序列最大子序和买卖股票的最佳时间1python，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.求最大非降子序列：

# -*- coding:utf-8 -*-
#@author：xinxinzhang
def lis(arr):
    d = [1] * len(arr)
    len_num = len(arr)
    for i in range(1,len_num):
        for j in range(i):
            if arr[j] <= arr[i] and d[i]<d[j]+1:#max{1,d[j]for j in range(i)+1}保证非降需 且取前面非降序长度最大的：
                d[i] = d[j] + 1
            if d[i] > len_num:
                d[i]=len_num
    return d[-1]


print(lis([3,2,1,5]))

2.求最大子序和：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

class Solution:
    def maxSubArray(self, a):
        """
        :type nums: List[int]
        :rtype: int
        """
        s=0
        max_s=a[0]
        for i in range(len(a)):
            s+=a[i]  #不断加下一个数
            if s>max_s:
                max_s=s
            if s<=0:#如果当前子列和为负数,则不可能使后面的部分和增大，则该抛弃掉
                s=0
        return max_s

3.买卖股票的最佳时间：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

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

这里上三种解法：

1.首先是由最长非降子串想到的双指针遍历的方法：但该方法俩循环，时间复杂度很大o（n^2）:

def maxProfit(prices):#超出时间限制
    maxpro=0
    for i in range(len(prices)):
        for j in range(i):
            if prices[j]<=prices[i]:
                d=prices[i]-prices[j]
                if d>maxpro:
                    maxpro=d
    return maxpro

leetcode会报超时

2.用动态规划求解：

还是有两种，一种直接用max，min，这种方法，时间会稍长一点：

def maxProfit(prices):#时间复杂度中等
    if not prices:
        return 0
    best_buy=prices[0]
    d=0
    for p in prices[1:]:
        d=max(d,p-best_buy)#最大利润=max（上一次利润，当前利润）
        best_buy=min(best_buy,p)#更新最佳买入点（价格最低的时候）
    return d

还一种思路与求最大子串和相似：

ef maxProfit(prices):#时间复杂度最小
    if not prices:
        return 0
    best_buy,d=prices[0],0
    for p in prices[1:]:
        if p<best_buy:
            best_buy=p
        elif p-best_buy>d:
            d=p-best_buy
    return d