算法（一）最大子數組問題

問題描述：

給你一個一維數組，數組值可正可負，要求得到連續子數組的最大和值，子數組的元素至少為1個。
           

解決方法：

暴力求解法：

通過兩層for循環周遊每一種可能的組合，再通過比較得到最大的值。方法實作較為簡單，但時間複雜度較高，需要O（n*n），代碼如下：

class Solution {
public:
    int maxSubArray(vector<int> & nums) {
        int number = nums.size();
        int currentSum = ;
        int max = nums[];
        //n個數則總共執行n次循環
        for (int i = ; i < number; ++i) {
            currentSum = ;
            for (int j = i; j < number; ++j) {
                currentSum += nums[j];
                if (currentSum > max)
                    max = currentSum;
            }
        }
        return max;
    }
};
           

分治法：

尋找數組的中間值，将原數組劃分為左右兩個部分，則最大子數組出現的可能情況有三種：
    1. 在左邊的子數組中
    2. 在右邊的子數組中
    3. 最大子數組跨越左右兩個子數組，則中間值middle一定包含在最大子數組中
實作代碼如下：
           

class Solution {
public:
    int maxSubArray(vector<int> & nums) {
        return findMaxSubArray(nums, , nums.size() - );
    }

    int findMaxSubArray(vector<int> & nums, int left, int right) {
        //當隻有一個值時傳回該值
        if (left == right)
            return nums[left];
        int mid = (left + right) / ;
        //左數組
        int leftMax = findMaxSubArray(nums, left, mid);
        //右數組
        int rightMax = findMaxSubArray(nums, mid + , right);
        //包含middle值的數組
        int centerMax = findCrossMaxArray(nums, mid, left, right);
        //傳回三者中的最大者
        return findMax(leftMax, rightMax, centerMax);
    }

    int findCrossMaxArray(vector<int> & nums, int mid, int left, int right) {
        int leftSum = , rightSum = ;
        int leftMax = nums[mid], rightMax = nums[mid + ];
        int i = mid, j = mid + ;
        int max = ;
        //左半邊最大的值
        for (; i >= left; --i) {
            leftSum += nums[i];
            if (leftSum > leftMax)
                leftMax = leftSum;
        }
        //右半邊最大的值
        for (; j <= right; ++j) {
            rightSum += nums[j];
            if (rightSum > rightMax)
                rightMax = rightSum;
        }
        max = leftMax + rightMax;
        return max;
    }

    int findMax(int a, int b, int c) {
        int temp = ;
        if (a > b)
            temp = a;
        else
            temp = b;
        if (temp < c)
            temp = c;
        return temp;
    }
};
           

這個算法的時間複雜度較暴力求解有了一定的提升。設數組的長度為n, 時間複雜度為T（n）,則時間複雜度為T（n） = 2 * T（n / 2） + 0(n)，可計算得時間複雜度為0（nlgn）。

線性時間算法

代碼如下：

class Solution {
public:
    int maxSubArray(vector<int> & nums) {
        int currentSum = ;
        int max = nums[];
        for (int i = ; i < nums.size(); ++i) {
            currentSum += nums[i];
            if (currentSum > max)
                max = currentSum;
            if (currentSum < )
                currentSum = ;
        }
        return max;
    }
};
           

從第一個數開始累加，如果是正的則一直保持，負的則舍棄重新累加。max一直保留目前的最大值。
           

動态規劃

該算法的思想是已知原數組後面部分的最大子數組nAll以及該部分最前一個元素開始的最大子數組nStart。然後再往前添加一個元素，則此時新數組的最大子數組要麼是包含新元素，要麼是原來的最大子數組。如果包含新元素，則是新元素本身或者是新元素加上原來的nStart的和。時間複雜度為O（n）。 代碼如下：

class Solution {
public:
    int maxSubArray(vector<int> & nums) {
        int nStart = nums[nums.size() - ];
        int nAll = nums[nums.size() - ];
        for (int i = nums.size() - ; i >= ; --i) {
            nStart = max(nums[i], nums[i] + nStart);
            nAll = max(nAll, nStart);
        }
        return nAll;
    }

    int max(int x, int y) {
        return (x > y) ? x : y;
    }
};
           

問題應用：

如果有一張近期股票的走勢圖，要問你哪天買入哪天賣出能得到最大收益。此時可以轉為最大子數組問題。數組元素為前後兩天的股票內插補點。