Code

2018年2月12日 星期一

Maximum subarray sum最大子字串和

Reference: Competitive Programmer's Handbook by Antti Laaksonen (2.4)

題目問的是,給一個字串,如:-1, 2, 4, -3, 5, 2, -5, 2,求連續子字串最大的和
上述例子的答案為10,因為2, 4, -3, 5, 2是總和最大的連續子字串

這題有三種解法,時間複雜度分別是O(n^3)O(n^2)O(n)

O(n^3)的解法很直觀,用三個for loop跑過每一個子字串:(function1)
第一個迴圈用來跑子字串的頭
第二個迴圈跑子字串的尾巴
第三個迴圈計算每一個子字串的總和

O(n^2)的解法是把三個for loop簡化為兩個,簡化的原理在於,第二個迴圈跑字串尾巴時就順便計算總和,過程中將最大的和記錄下來(best),如此便不需要第三個迴圈了。(function2)

O(n)的解法由J. B. Kadane想出,有時被稱為Kadane's algorithm,中心原理在於,index每到達一個元素的位置時,都確保擁有「以該位置為結尾的子字串」的最大和。
(若該和為負並且小於下一個元素的值,則被取代 。若為正數,則無論下一個元素的值是否大於它,都會累加。判斷的依據可以想成,加了下一個元素,和會不會變大?捨棄前面元素的和,只從下一個元素開始計算,能否獲得更大的和?)(function3)

#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

void function1(int array[]){
    int best = INT_MIN;
    for (int i = 0; i < 8; i++) {
        for (int j = i; j < 8; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += array[k];
            }
            best = max(best, sum);
        }
    }
    cout << best << endl;
}

void function2(int array[]){
    int best = INT_MIN;
    for (int i = 0; i < 8; i++) {
        int sum = 0;
        for (int j = i; j < 8; j++) {
            sum += array[j];
            best = max(best, sum);
        }
    }
    cout << best << endl;
}

void function3(int array[]){
    int best = INT_MIN, sum = 0;
    for (int i = 0; i < 8; i++) {
        sum = max(array[i], sum + array[i]);
        /*以第i-1位為結尾的子字串是否要加上第i位元素,或捨棄只取第i位元素,才能獲得最大和*/
        best = max(best, sum);
    }
    cout << best << endl;
}


int main(int argc, const char * argv[]) {
    int a[] = {-1, 2, 4, -3, 5, 2, -5, 2};
    function1(a);
    function2(a);
    function3(a);
    return 0;
}

沒有留言:

張貼留言