題目

給出N個整數數列，請找出該數列連續元素的最大和。

Example 1:
Input: [1,2,-3,4,5]
Output: 9

Example 2:
Input: [10,-5,7,6,-1,-3]
Output: 13

Example 3:
Input: [-1,-2,-3,5,6,-1,10,11,-3]
Output: 21

Example 4:
Input: [1,2,3,2,1,1]
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

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

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

    max_sum = arr[0]  # 最大的總和
    sum_ = arr[0]  # 當前計算的總和，初始化陣列第一個數值
    prev_sub = 0  # 紀錄前次為正連續數列或負連續數列, 例如: [1,2,3,2,1]，連續組合應為[1,2,3]或[3,2,1]

    for i in range(0, len(arr) - 1):
        sub = arr[i] - arr[i + 1]

        if prev_sub == 0:
            prev_sub = sub

        if sub == 1 and prev_sub == sub:  # 負連續數列
            # 當前數值與下一個數值差值為1代表為負連續數值，例如: 3,2 or 2,1 or 1,0
            sum_ += arr[i + 1]
            prev_sub = sub
            use_if = '負連續數列處理'
        elif sub == -1 and prev_sub == sub:  # 正連續數列
            # 當前數值與下一個數值差值為-1代表為正連續數值，例如: 0,1 or 1,2 or 2,3
            sum_ += arr[i + 1]
            prev_sub = sub
            use_if = '正連續數列處理'
        else:
            # 反之差值不為1或-1代表為非連續數值，則把下一個數值當作新的總和初始值
            sum_ = arr[i + 1]
            prev_sub = 0
            use_if = '不連續處理'

        # 『當前計算的總和』如果大於『最大總和』，則把『當前計算的總和』設定給『最大總和』
        if sum_ >= max_sum:
            max_sum = sum_

        n = str(arr[i]).rjust(3, " ")
        n2 = str(arr[i + 1]).rjust(3, " ")
        p_sub = str(sub).rjust(3, " ")
        p_sum_ = str(sum_).rjust(2, " ")
        p_max_sum = str(max_sum).rjust(2, " ")
        print(
            f'Step {i + 1}: (n:{n} , n+1:{n2})={p_sub}, sum_:{p_sum_}, max_sum: {p_max_sum} | {use_if}')

    print(f'output: max_sum: {max_sum}')


test_case1 = [1, 2, -3, 4, 5]
test_case2 = [10, -5, 7, 6, -1, -3]
test_case3 = [-1, -2, -3, 5, 6, -1, 10, 11, -3]
test_case4 = [1, 2, 3, 2, 1, 1]
count_max_sum(test_case1)
count_max_sum(test_case2)
count_max_sum(test_case3)
count_max_sum(test_case4)

"""
Result:
====================================
input: [1, 2, -3, 4, 5]
Step 1: (n:  1, n+1:  2)= -1, sum_: 3, max_sum:  3 | 正連續數列處理
Step 2: (n:  2, n+1: -3)=  5, sum_:-3, max_sum:  3 | 不連續處理
Step 3: (n: -3, n+1:  4)= -7, sum_: 4, max_sum:  4 | 不連續處理
Step 4: (n:  4, n+1:  5)= -1, sum_: 9, max_sum:  9 | 正連續數列處理
output: max_sum: 9
====================================
input: [10, -5, 7, 6, -1, -3]
Step 1: (n: 10, n+1: -5)= 15, sum_:-5, max_sum: 10 | 不連續處理
Step 2: (n: -5, n+1:  7)=-12, sum_: 7, max_sum: 10 | 不連續處理
Step 3: (n:  7, n+1:  6)=  1, sum_:13, max_sum: 13 | 負連續數列處理
Step 4: (n:  6, n+1: -1)=  7, sum_:-1, max_sum: 13 | 不連續處理
Step 5: (n: -1, n+1: -3)=  2, sum_:-3, max_sum: 13 | 不連續處理
output: max_sum: 13
====================================
input: [-1, -2, -3, 5, 6, -1, 10, 11, -3]
Step 1: (n: -1, n+1: -2)=  1, sum_:-3, max_sum: -1 | 負連續數列處理
Step 2: (n: -2, n+1: -3)=  1, sum_:-6, max_sum: -1 | 負連續數列處理
Step 3: (n: -3, n+1:  5)= -8, sum_: 5, max_sum:  5 | 不連續處理
Step 4: (n:  5, n+1:  6)= -1, sum_:11, max_sum: 11 | 正連續數列處理
Step 5: (n:  6, n+1: -1)=  7, sum_:-1, max_sum: 11 | 不連續處理
Step 6: (n: -1, n+1: 10)=-11, sum_:10, max_sum: 11 | 不連續處理
Step 7: (n: 10, n+1: 11)= -1, sum_:21, max_sum: 21 | 正連續數列處理
Step 8: (n: 11, n+1: -3)= 14, sum_:-3, max_sum: 21 | 不連續處理
output: max_sum: 21
====================================
input: [1, 2, 3, 2, 1, 1]
Step 1: (n:  1, n+1:  2)= -1, sum_: 3, max_sum:  3 | 正連續數列處理
Step 2: (n:  2, n+1:  3)= -1, sum_: 6, max_sum:  6 | 正連續數列處理
Step 3: (n:  3, n+1:  2)=  1, sum_: 2, max_sum:  6 | 不連續處理
Step 4: (n:  2, n+1:  1)=  1, sum_: 3, max_sum:  6 | 負連續數列處理
Step 5: (n:  1, n+1:  1)=  0, sum_: 1, max_sum:  6 | 不連續處理
output: max_sum: 6


"""

Keyword

1
2
3
演算法, Algorithm, al-go-rithm
計算, count
連續數列, Consecutive, con-se-cu-tive