Codility每周一课：L9 Maximum slice pr

9.png

P9.2 MaxProfit

Given a log of stock prices compute the maximum possible earning.

• P9.2 最大利润
  计算多股股票可能获得的最大利润

一个包含N个元素的数组A，每个元素表示公司股票的每日价格(美分)。

编写函数：

def solution(A)

返回在这段时间内每份可能获得的最大收益(美分)。如果不能获得任何收益，则返回零。也就是说函数应返回max{0, A[m]−A[k] : 0 ≤ k < m < N }

例如，给出N=6的数组A：

A[0]=23171，A[1]=21011，A[2]=21123，A[3]=21366，A[4]=21013，A[5]=21367

函数应返回356: 在股票价格为210.11美元时买进，而在213.67美元时卖出，则获得最大收益为3.56美元，也就是356美分。 数组A可能包含上百兆字节。

假定:

1. N是区间[0，400,000]内的整数；

2. 数组A的每个元素都是区间[0，200,000]内的整数；

• 解题思路

遍历数组，得到的第一个数看作进价。如果下一个数小于等于进价，并且出价已经不是初始值，则存储出价减去进价的利润值，并且更新进价，出价定义为初始值。如果大于出价，则更新出价值。最后在利润列表中获得最大的。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 9：Maximum slice problem
# P 9.2 MaxProfit


def solution(A):
    """
    返回数组A所代表的股价，可以获得的利润的最大值
    :param A: 股价数组
    :return: 最大利润
    """
    if len(A) == 1:
        return 0
    else:
        profit = [0]  # 最小利润就是0，此处设置是为了编程方便，否则后文需要增加判断非负的条件
        buy, sell = -1, -1
        for i in A:
            if buy == -1:
                buy = i
            else:
                if sell == -1 and i > buy:
                    sell = i
                elif sell != -1 and i > sell:
                    sell = i
                elif i < buy:
                    if sell != -1:
                        profit.append(sell - buy)
                    buy = i
                    sell = -1
        profit.append(sell - buy)
        return max(profit)

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image