蚂蚁金服笔试题 0929

题目

小红准备进行一番基金操作来赚钱，她找到了一支基金，准备对这支基金进行一些操作。已知该基金每天的价格都会变化，小红每天可以花费当天的价格买入一笔基金，或者以当天的价格卖出一笔基金（前提是手上至少持有一笔基金）。小红有一个超能力，她可以直接预测到接下来的n天，每天基金价格的变化，但小红为了避免打草惊蛇，她的基金买卖有以下限制：每天最多买入/卖出一笔基金（例如手上如果有2笔基金，那么最多只能卖出1笔，另一笔只能等到以后再卖）。手上最多持有2笔基金。由于小红没有得知n天以后的情况，所以她计划在第n天时，手上为未持有基金的状态。小红想知道，自己在这n天中最多可以赚多少钱？假设小红的本金是足够多的，且初始状态是未购买基金。

输入描述

第一行输入一个正整数n，代表小红内幕消息得知的天数。

第二行输入n个正整数ai。代表第i天基金的价格。

1 ≤ n ≤ 100000

1 ≤ ai ≤ 10^9

输出描述

一个整数，代表最终小红能赚的最大钱数。

样例输入一

5

1 2 3 4 5

样例输出一

6

说明：第一天买入一笔，第二天买入一笔，第三天不操作，第四天卖出一笔，第五天卖出一笔，总共赚了6元。

样例输入二

4

4 2 3 1

样例输出二

1

说明：第一天不操作，第二天买入一笔，第三天卖出，第四天不操作。

以下是自己参考别人的思路，写的python代码。

j=0，当天不持有基金；j=1，当天持有一份基金；j=2，当天持有两份基金。

n = 6
prices = [1, 2, 3, 4, 5, 6]
# prices = [4, 2, 3, 1]

dp = [[0 for _ in range(3)] for _ in range(n)]

dp[0][1] = -prices[0] 
dp[0][2] = -1e7

for i in range(1, n):
    for j in range(3):
        if j == 0:
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            
        if j == 1:
            dp[i][1] = max(dp[i-1][1], dp[i-1][2] + prices[i], dp[i-1][0] - prices[i])
            
        if j == 2:
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i])
            
        
print(dp[n-1][0])