題目

以下範例中的陣列數值代表每天的股價，在只能有交易一次的條件下，請找出最多能賺多少錢

範例：
Example 1:
Input: [7,1,5,3,6,4]
Output: 5

Example 2:
Input: [7,6,4,3,1]
Output: 0

Example 3:
Input: [1,2,3,2,1]
Output: 2

Example 4:
Input: [1,2,3,2,1,7]
Output: 6

解法一

Github code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
"""
思路：
1.一個完整交易包含買進和賣出，輸入陣列最後一筆股價是不能用來做買入
2.[(n+1)天股價-n天股價]比[n天股價-(n-1)天股價]大，就可以當作最佳獲利
3.從第二點條件來看則需要兩個回圈，外圈從n天買入開始，內圈從n+1天賣出結束，最後一次買入為len(arr)-1
"""


def find_the_best_deal(arr):
    if len(arr) == 0:
        print('input is empty.')
        return 0

    print(f'====================================')
    print(f'input: {arr}')

    best_profit = 0  # 最佳獲利

    for i in range(0, len(arr) - 1):
        for j in range(i + 1, len(arr)):
            profit = arr[j] - arr[i]  # 計算當前交易的獲利
            if profit > best_profit:
                best_profit = profit

            buy_price = str(arr[i]).rjust(1, " ")
            sell_price = str(arr[j]).rjust(1, " ")
            profit_price = str(profit).rjust(2, " ")
            best_profit_price = str(best_profit).rjust(2, " ")
            print(
                f'第{i + 1}天買入股價:{buy_price}, 第{j + 1}天賣出股價:{sell_price}, 當次獲利:{profit_price}, 最佳獲利:{best_profit_price}')
        print()

    print(f'output: 最佳獲利為 {best_profit}')


test_case1 = [7, 1, 5, 3, 6, 4]
test_case2 = [7, 6, 4, 3, 1]
test_case3 = [1, 2, 3, 2, 1]
test_case4 = [1, 2, 3, 2, 1, 7]

find_the_best_deal(test_case1)
find_the_best_deal(test_case2)
find_the_best_deal(test_case3)
find_the_best_deal(test_case4)

"""
Result:
====================================
input: [7, 1, 5, 3, 6, 4]
第1天買入股價:7, 第2天賣出股價:1, 當次獲利:-6, 最佳獲利: 0
第1天買入股價:7, 第3天賣出股價:5, 當次獲利:-2, 最佳獲利: 0
第1天買入股價:7, 第4天賣出股價:3, 當次獲利:-4, 最佳獲利: 0
第1天買入股價:7, 第5天賣出股價:6, 當次獲利:-1, 最佳獲利: 0
第1天買入股價:7, 第6天賣出股價:4, 當次獲利:-3, 最佳獲利: 0

第2天買入股價:1, 第3天賣出股價:5, 當次獲利: 4, 最佳獲利: 4
第2天買入股價:1, 第4天賣出股價:3, 當次獲利: 2, 最佳獲利: 4
第2天買入股價:1, 第5天賣出股價:6, 當次獲利: 5, 最佳獲利: 5
第2天買入股價:1, 第6天賣出股價:4, 當次獲利: 3, 最佳獲利: 5

第3天買入股價:5, 第4天賣出股價:3, 當次獲利:-2, 最佳獲利: 5
第3天買入股價:5, 第5天賣出股價:6, 當次獲利: 1, 最佳獲利: 5
第3天買入股價:5, 第6天賣出股價:4, 當次獲利:-1, 最佳獲利: 5

第4天買入股價:3, 第5天賣出股價:6, 當次獲利: 3, 最佳獲利: 5
第4天買入股價:3, 第6天賣出股價:4, 當次獲利: 1, 最佳獲利: 5

第5天買入股價:6, 第6天賣出股價:4, 當次獲利:-2, 最佳獲利: 5

output: 最佳獲利為 5
====================================
input: [7, 6, 4, 3, 1]
第1天買入股價:7, 第2天賣出股價:6, 當次獲利:-1, 最佳獲利: 0
第1天買入股價:7, 第3天賣出股價:4, 當次獲利:-3, 最佳獲利: 0
第1天買入股價:7, 第4天賣出股價:3, 當次獲利:-4, 最佳獲利: 0
第1天買入股價:7, 第5天賣出股價:1, 當次獲利:-6, 最佳獲利: 0

第2天買入股價:6, 第3天賣出股價:4, 當次獲利:-2, 最佳獲利: 0
第2天買入股價:6, 第4天賣出股價:3, 當次獲利:-3, 最佳獲利: 0
第2天買入股價:6, 第5天賣出股價:1, 當次獲利:-5, 最佳獲利: 0

第3天買入股價:4, 第4天賣出股價:3, 當次獲利:-1, 最佳獲利: 0
第3天買入股價:4, 第5天賣出股價:1, 當次獲利:-3, 最佳獲利: 0

第4天買入股價:3, 第5天賣出股價:1, 當次獲利:-2, 最佳獲利: 0

output: 最佳獲利為 0
====================================
input: [1, 2, 3, 2, 1]
第1天買入股價:1, 第2天賣出股價:2, 當次獲利: 1, 最佳獲利: 1
第1天買入股價:1, 第3天賣出股價:3, 當次獲利: 2, 最佳獲利: 2
第1天買入股價:1, 第4天賣出股價:2, 當次獲利: 1, 最佳獲利: 2
第1天買入股價:1, 第5天賣出股價:1, 當次獲利: 0, 最佳獲利: 2

第2天買入股價:2, 第3天賣出股價:3, 當次獲利: 1, 最佳獲利: 2
第2天買入股價:2, 第4天賣出股價:2, 當次獲利: 0, 最佳獲利: 2
第2天買入股價:2, 第5天賣出股價:1, 當次獲利:-1, 最佳獲利: 2

第3天買入股價:3, 第4天賣出股價:2, 當次獲利:-1, 最佳獲利: 2
第3天買入股價:3, 第5天賣出股價:1, 當次獲利:-2, 最佳獲利: 2

第4天買入股價:2, 第5天賣出股價:1, 當次獲利:-1, 最佳獲利: 2

output: 最佳獲利為 2
====================================
input: [1, 2, 3, 2, 1, 7]
第1天買入股價:1, 第2天賣出股價:2, 當次獲利: 1, 最佳獲利: 1
第1天買入股價:1, 第3天賣出股價:3, 當次獲利: 2, 最佳獲利: 2
第1天買入股價:1, 第4天賣出股價:2, 當次獲利: 1, 最佳獲利: 2
第1天買入股價:1, 第5天賣出股價:1, 當次獲利: 0, 最佳獲利: 2
第1天買入股價:1, 第6天賣出股價:7, 當次獲利: 6, 最佳獲利: 6

第2天買入股價:2, 第3天賣出股價:3, 當次獲利: 1, 最佳獲利: 6
第2天買入股價:2, 第4天賣出股價:2, 當次獲利: 0, 最佳獲利: 6
第2天買入股價:2, 第5天賣出股價:1, 當次獲利:-1, 最佳獲利: 6
第2天買入股價:2, 第6天賣出股價:7, 當次獲利: 5, 最佳獲利: 6

第3天買入股價:3, 第4天賣出股價:2, 當次獲利:-1, 最佳獲利: 6
第3天買入股價:3, 第5天賣出股價:1, 當次獲利:-2, 最佳獲利: 6
第3天買入股價:3, 第6天賣出股價:7, 當次獲利: 4, 最佳獲利: 6

第4天買入股價:2, 第5天賣出股價:1, 當次獲利:-1, 最佳獲利: 6
第4天買入股價:2, 第6天賣出股價:7, 當次獲利: 5, 最佳獲利: 6

第5天買入股價:1, 第6天賣出股價:7, 當次獲利: 6, 最佳獲利: 6

output: 最佳獲利為 6


"""

Keyword

1
2
3
4
5
演算法, Algorithm, al-go-rithm
獲利, profit, pro-fit
交易, trade, trade
交易, deal, deal