簡介

最大子序列 (Maximum Subarray 或稱作 Maximum Subsequence) 為在一個具有正負數陣列當中，找出一段連續的元素總和最大，這個問題又分為一定要取值或可不取。實作方法有很多種，這裡說明四種實作方法，分別為暴力法、改良式暴力法、Divide and Conquer 和 Kadane’s 演算法 (Dynamic Programming)，其中 Kadane’s 實作取值和可不取值兩種版本，其他為一定要取值版本。
最大子序列

演算法

暴力法

最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可，[0] ~ [0]、[0] ~ [1] … [0] ~ [N] … [N] ~ [N] 的總和找出最大。

改良式暴力法

然而在上面暴力法計算，[0] ~ [N] 的總和時，其實過程中 [0] ~ [0]、[0] ~ [1] … [0] ~ [N] 的總和也已經同時計算了，所以只需計算 [0] ~ [N]、[1] ~ [N] … [N] ~ [N] 即可。

Divide and Conquer

如下圖所示，Divide and Conquer 的基本概念是，將數列分成兩塊，各自回報最大的值，如藍色部分；然而這是最大子序列不只會出現在左邊或右邊，也有可能出現橫跨兩邊的紅色區域，所以還要再找出紅色區域的最大值。由於紅色區域表示的是橫跨兩邊，所以只要考慮包含中點的情況，如圖紅色元素與綠色區域，最後最大子序列的值即為紅色區域或藍色區域的最大值。
Divide and Conquer

Kadane’s 演算法

Kadane’s 演算法為 Dynamic Programming (動態規劃) 方式，概念上其實是很直覺的思考，如下圖所示，當計算前四個元素的時候，前面總和是 1、3 和 6，很明顯列入計算是有幫助的，故我們會納入計算，但是到了第五個元素的時候，前面總和變成 -1，若列入計算會拉低分數，故我們不列入計算；由以上簡單的範例可知，當連續總和是正的時候，可以繼續列入計算，當為負的時候，則不列入計算，也就是重新重 0 開始。不過也因為這樣的演算法特性，原始版本無法是一定要取值的版本，必須做額外的處理。
Kadane's 演算法

分析

時間複雜度

  • 暴力法：O(n3)
  • 改良式暴力法：O(n2)
  • Divide and Conquer：O(nlog n)
  • Kadane’s 演算法：O(n)

語法

C#

暴力法

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaximumSubsequence
{
    // O(n^3)
    class BruteForce
    {
        public static int GetMax(int[] array)
        {
            int max = array[0], sum;
            for (int start = 0; start < array.Length; ++start)
                for (int end = 0; end < array.Length; ++end)
                {
                    sum = 0;
                    for (int i = start; i <= end; ++i)
                        sum += array[i];
                    max = Math.Max(max, sum);
                }
            return max;
        }
    }
}

改良式暴力法

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaximumSubsequence
{
    // O(n^2)
    class RefineBruteForce
    {
        public static int GetMax(int[] array)
        {
            int max = array[0], sum;
            for (int start = 0; start < array.Length; ++start)
            {
                sum = 0;
                for (int i = start; i < array.Length; ++i)
                {
                    sum += array[i];
                    max = Math.Max(max, sum);
                }
            }
            return max;
        }
    }
}

Divide and Conquer

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaximumSubsequence
{
    // O(nlogn)
    class DivideAndConquer
    {
        public static int GetMax(int[] array)
        {
            return GetMax(array, 0, array.Length - 1);
        }

        private static int GetMax(int[] array, int start, int end)
        {
            if (start == end)
                return array[start];

            int middle = (start + end) / 2;
            int leftMax = GetMax(array, start, middle);
            int rightMax = GetMax(array, middle + 1, end);

            int cross = GetCrossMax(array, start, middle, end);

            return Math.Max(Math.Max(leftMax, rightMax), cross);
        }

        private static int GetCrossMax(int[] array, int start, int middle, int end)
        {
            int leftMax = array[middle], leftSum = 0;
            int rightMax = array[middle + 1], rightSum = 0;
            for (int i = middle; i >= start; --i)
            {
                leftSum += array[i];
                leftMax = Math.Max(leftMax, leftSum);
            }
            for (int i = middle + 1; i <= end; ++i)
            {
                rightSum += array[i];
                rightMax = Math.Max(rightMax, rightSum);
            }

            return Math.Max(Math.Max(leftMax, rightMax), leftMax + rightMax);
        }
    }
}

Kadane’s 演算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaximumSubsequence
{
    // O(n), Kadane's 演算法 (dynamic porgramming), 可不取版本
    class Kadanes
    {
        public static int GetMax(int[] array)
        {
            int sum = 0;
            int max = array[0];
            for (int i = 0; i < array.Length; ++i)
            {
                sum += array[i];
                sum = Math.Max(0, sum);
                max = Math.Max(sum, max);
            }
            return max;
        }
    }
}

Kadane’s 演算法 (一定要取值版本)

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaximumSubsequence
{
    // O(n), Kadane's 演算法 (dynamic porgramming), 至少取一個版本
    class KadanesOne
    {
        public static int GetMax(int[] array)
        {
            int sum = Detect(array);
            if (sum < 0)
                return sum;
            int max = array[0];
            for (int i = 0; i < array.Length; ++i)
            {
                sum += array[i];
                sum = Math.Max(0, sum);
                max = Math.Max(sum, max);
            }
            return max;
        }

        // 測試是否全為負數，是的話回傳最大的負數，否則回傳 0
        private static int Detect(int[] array)
        {
            int max = array[0];
            for (int i = 0; i < array.Length; ++i)
            {
                if (array[i] >= 0)
                    return 0;
                max = Math.Max(array[i], max);
            }
            return max;
        }
    }
}

Java

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// O(n^3)
public class BruteForce {
    public static int GetMax(int[] array)
    {
        int max = array[0], sum;
        for (int start = 0; start < array.length; ++start)
            for (int end = 0; end < array.length; ++end)
            {
                sum = 0;
                for (int i = start; i <= end; ++i)
                    sum += array[i];
                max = Math.max(max, sum);
            }
        return max;
    }
}

改良式暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// O(n^2)
public class RefineBruteForce {
    public static int GetMax(int[] array)
    {
        int max = array[0], sum;
        for (int start = 0; start < array.length; ++start)
        {
            sum = 0;
            for (int i = start; i < array.length; ++i)
            {
                sum += array[i];
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}

Divide and Conquer

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
// O(nlogn)
public class DivideAndConquer {
    public static int GetMax(int[] array)
    {
        return GetMax(array, 0, array.length - 1);
    }

    private static int GetMax(int[] array, int start, int end)
    {
        if (start == end)
            return array[start];

        int middle = (start + end) / 2;
        int leftMax = GetMax(array, start, middle);
        int rightMax = GetMax(array, middle + 1, end);

        int cross = GetCrossMax(array, start, middle, end);

        return Math.max(Math.max(leftMax, rightMax), cross);
    }

    private static int GetCrossMax(int[] array, int start, int middle, int end)
    {
        int leftMax = array[middle], leftSum = 0;
        int rightMax = array[middle + 1], rightSum = 0;
        for (int i = middle; i >= start; --i)
        {
            leftSum += array[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        for (int i = middle + 1; i <= end; ++i)
        {
            rightSum += array[i];
            rightMax = Math.max(rightMax, rightSum);
        }

        return Math.max(Math.max(leftMax, rightMax), leftMax + rightMax);
    }
}

Kadane’s 演算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// O(n), Kadane's 演算法 (dynamic porgramming), 可不取版本
public class Kadanes {
    public static int GetMax(int[] array)
    {
        int sum = 0;
        int max = array[0];
        for (int i = 0; i < array.length; ++i)
        {
            sum += array[i];
            sum = Math.max(0, sum);
            max = Math.max(sum, max);
        }
        return max;
    }
}

Kadane’s演算法 (一定要取值版本)

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
// O(n), Kadane's 演算法 (dynamic porgramming), 至少取一個版本
public class KadanesOne {
    public static int GetMax(int[] array)
    {
        int sum = Detect(array);
        if (sum < 0)
            return sum;
        int max = array[0];
        for (int i = 0; i < array.length; ++i)
        {
            sum += array[i];
            sum = Math.max(0, sum);
            max = Math.max(sum, max);
        }
        return max;
    }

    // 測試是否全為負數，是的話回傳最大的負數，否則回傳 0
    private static int Detect(int[] array)
    {
        int max = array[0];
        for (int i = 0; i < array.length; ++i)
        {
            if (array[i] >= 0)
                return 0;
            max = Math.max(array[i], max);
        }
        return max;
    }
}

C++

暴力法

BruteForce.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef BRUTEFORCE_H
#define BRUTEFORCE_H
#include <algorithm>
using namespace std;

class BruteForce
{
    public:
        static int GetMax(int* array, int length);
    protected:
    private:
};

#endif // BRUTEFORCE_H

BruteForce.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "BruteForce.h"

int BruteForce::GetMax(int* array, int length)
{
    int max_sum = array[0], sum;
    for (int start = 0; start < length; ++start)
        for (int end = 0; end < length; ++end)
        {
            sum = 0;
            for (int i = start; i <= end; ++i)
                sum += array[i];
            max_sum = max(max_sum, sum);
        }
    return max_sum;
}

改良式暴力法

RefineBruteForce.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef REFINEBRUTEFORCE_H
#define REFINEBRUTEFORCE_H
#include <algorithm>
using namespace std;

class RefineBruteForce
{
    public:
        static int GetMax(int* array, int length);
    protected:
    private:
};

#endif // REFINEBRUTEFORCE_H

RefineBruteForce.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "RefineBruteForce.h"

int RefineBruteForce::GetMax(int* array, int length)
{
    int max_sum = array[0], sum;
    for (int start = 0; start < length; ++start)
    {
        sum = 0;
        for (int i = start; i < length; ++i)
        {
            sum += array[i];
            max_sum = max(max_sum, sum);
        }
    }
    return max_sum;
}

Divide and Conquer

DivideAndConquer.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef DIVIDEANDCONQUER_H
#define DIVIDEANDCONQUER_H
#include <algorithm>
using namespace std;

class DivideAndConquer
{
    public:
        static int GetMax(int* array, int length);
        static int GetMax(int* array, int length, int start, int end);
        static int GetCrossMax(int* array, int length, int start, int middle, int end);
    protected:
    private:
};

#endif // DIVIDEANDCONQUER_H

DivideAndConquer.cpp

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
#include "DivideAndConquer.h"

int DivideAndConquer::GetMax(int* array, int length)
{
    return DivideAndConquer::GetMax(array, length, 0, length - 1);
}

int DivideAndConquer::GetMax(int* array, int length, int start, int end)
{
    if (start == end)
        return array[start];

    int middle = (start + end) / 2;
    int leftMax = DivideAndConquer::GetMax(array, length, start, middle);
    int rightMax = DivideAndConquer::GetMax(array, length, middle + 1, end);

    int cross = DivideAndConquer::GetCrossMax(array, length, start, middle, end);

    return max(max(leftMax, rightMax), cross);
}

int DivideAndConquer::GetCrossMax(int* array, int length, int start, int middle, int end)
{
    int leftMax = array[middle], leftSum = 0;
    int rightMax = array[middle + 1], rightSum = 0;
    for (int i = middle; i >= start; --i)
    {
        leftSum += array[i];
        leftMax = max(leftMax, leftSum);
    }
    for (int i = middle + 1; i <= end; ++i)
    {
        rightSum += array[i];
        rightMax = max(rightMax, rightSum);
    }

    return max(max(leftMax, rightMax), leftMax + rightMax);
}

Kadane’s 演算法

KadanesOne.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef KADANES_H
#define KADANES_H
#include <algorithm>
using namespace std;

class Kadanes
{
    public:
        static int GetMax(int* array, int length);
    protected:
    private:
};

#endif // KADANES_H

KadanesOne.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "Kadanes.h"

// O(n), Kadane's 演算法 (dynamic porgramming), 可不取版本
int Kadanes::GetMax(int* array, int length)
{
    int sum = 0;
    int max_sum = array[0];
    for (int i = 0; i < length; ++i)
    {
        sum += array[i];
        sum = max(0, sum);
        max_sum = max(sum, max_sum);
    }
    return max_sum;
}

Kadane’s 演算法 (一定要取值版本)

Kadanes.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef KADANESONE_H
#define KADANESONE_H
#include <algorithm>
using namespace std;

class KadanesOne
{
    public:
        static int GetMax(int* array, int length);
        static int Detect(int* array, int length);
    protected:
    private:
};

#endif // KADANESONE_H

Kadanes.cpp

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
#include "KadanesOne.h"

// O(n), Kadane's 演算法 (dynamic porgramming), 至少取一個版本
int KadanesOne::GetMax(int* array, int length)
{
    int sum = KadanesOne::Detect(array, length);
    if (sum < 0)
        return sum;
    int max_sum = array[0];
    for (int i = 0; i < length; ++i)
    {
        sum += array[i];
        sum = max(0, sum);
        max_sum = max(sum, max_sum);
    }
    return max_sum;
}

// 測試是否全為負數，是的話回傳最大的負數，否則回傳 0
int KadanesOne::Detect(int* array, int length)
{
    int max_sum = array[0];
    for (int i = 0; i < length; ++i)
    {
        if (array[i] >= 0)
            return 0;
        max_sum = max(array[i], max_sum);
    }
    return max_sum;
}

隨機產生 100000 筆資料實測，Java 的暴力法異常的快，另外 BruteForce 還是忘記他吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
C#
Kadanes: 10ms
KadanesOne: 0ms
DivideAndConquer: 20-30ms
RefineBruteForce: 36000ms

Java
Kadanes: 40-50ms
KadanesOne: 0ms
DivideAndConquer: 30-40ms
RefineBruteForce: 8000ms

C++
Kadanes: 10ms
KadanesOne: 0ms
DivideAndConquer: 20-30ms
RefineBruteForce: 36000ms

延伸閱讀

動態規劃 (Dynamic Programming)
分治法 (Divide and conquer)