簡介

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

Fig-4-3-Maximum-Subarray    

暴力法

最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可,[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的基本概念是,將數列分成兩塊,各自回報最大的值,如藍色部分;然而這是最大子序列不只會出現在左邊或右邊,也有可能出現橫跨兩邊的紅色區域,所以還要再找出紅色區域的最大值。由於紅色區域表示的是橫跨兩邊,所以只要考慮包含中點的情況,如圖紅色元素與綠色區域,最後最大子序列的值即為紅色區域或藍色區域的最大值。

max

Kadane's演算法

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

max  

分析

時間複雜度

暴力法:O(n3)

改良式暴力法:O(n2)

Divide and Conquer:O(nlog n)

Kadane's演算法:O(n)

語法

C#

暴力法

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;
        }
    }
}

改良式暴力法

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

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演算法

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演算法(一定要取值版本)

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

暴力法

// 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;
    }
}

改良式暴力法

// 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

// 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演算法

// 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演算法(一定要取值版本)

// 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

#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

#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

#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

#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

#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

#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

#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

#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

#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

#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還是忘記他吧

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

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()