leetcode394，Leetcode OJ: Maximun Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array?[?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray?[4,?1,2,1]?has the largest sum =?6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

求子串最大和，第一次看到這題是在sogou的筆試，當時手寫代碼，用了動態規劃，以為就OK，誰知道在LeetCode上一敲各種bug。。

不過，總的思想是沒有錯的，只是要注意的點比較多，雖然不是最優的解法，但也陳述一下吧。

leetcode394，LZ先把問題想了想，求子串和最大，那什么是子串？拿以上數組為例，我們把子串的兩邊劃出來。

?[?2,1,?3, | 4,?1,2,1, |?5,4]

紅豎杠間是我們要最大和的子串，那么就是要左右兩側的子串和最小，那么就是兩側的和都分別最小則總和最小，即中間的子串即為最大。

以上說的是中心思想，但這里還有好多的情況要討論。

當紅線重合時，那么就是沒有子串，則需要其中一條紅線左移，或者右移一格。

當只有一條紅線時，即只考慮左側子串，或右側子串時，也要獨立考慮。

提交了N次才通過的代碼：

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n == 1)
            return A[0];
        vector<int> fsum(n-1, 0), bsum(n-1, 0);
        vector<bool> fflag(n-1, false), bflag(n-1, false);
        int tsum = A[0];
        fsum[0] = A[0];
        fflag[0] = true;
        
        for (int i = 1; i < n-1; ++i) {
            tsum += A[i];
            if (tsum < fsum[i-1]) {
                fsum[i] = tsum;
                fflag[i] = true;
            } else {
                fsum[i] = fsum[i-1];
            }
        }
        tsum = A[n-1];
        bsum[n-2] = A[n-1];
        bflag[n-2] = true;
        for (int i = n-2; i > 0; --i) {
            tsum += A[i];
            if (tsum < bsum[i]) {
                bsum[i-1] = tsum;
                bflag[i-1] = true;
            } else {
                bsum[i-1] = bsum[i];
            }
        }
        tsum += A[0];
        int ret = tsum;
        for (int i = 0; i < n-1; ++i) {
            int tmp = tsum - min(fsum[i], bsum[i]);  // 只考慮左側或右側
            if (!fflag[i] || !bflag[i]) { // 分隔線不重合
                if (tmp < tsum - fsum[i] - bsum[i])
                    tmp = tsum - fsum[i] - bsum[i];
            } else {  // 分隔線重合
                if (i > 0 && tmp < tsum - fsum[i-1] - bsum[i]) {
                    tmp = tsum - fsum[i-1] - bsum[i];
                }
                if (i < n-2 && tmp < tsum - fsum[i] - bsum[i+1]) {
                    tmp = tsum - fsum[i] - bsum[i+1];
                }
            }
            if (tmp > ret) {
                ret = tmp;
            }
        }
        return ret;
    }
};

成功拖低了平均水平，然后實在想知道有沒更好的方法，上網一搜果斷有的，找到了傳說中的Kadane算法（自行百度吧），代碼只有幾行（傷透了我的心。。），這里直接貼一下吧：

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int ans = 0, maxn = INT_MIN;  
        for(int i = 0; i < n; i++){  
            if(ans < 0) ans = 0;  
            ans += A[i];  
            maxn = max(maxn, ans);   
        }  
        return maxn;  
    }
};

然后LZ蛋疼地去看下運行時間，發現居然比我的方法慢？不能理解。多提交了幾次，也是這樣，于是想了想，發現這代碼里面用了max函數，而且每次都要重要賦值，其實可以先判斷再賦值。LZ加了個判斷再賦值，然后提交，果斷快了，嗯，這是小插曲，大家可以不用管LZ自娛自樂。

然后就是分治的思路了，這個其實我也不太懂，不過看別人的代碼確實還是學了不少的，直接轉別人的代碼吧（以上Kadane算法也是別人的代碼）。

三個狀態：begin, end, mid=(begin+end)/2

leetcode121。1. 在A[begin..mid-1]間

2. 在A[mid+1..end]間

3. 包含A[mid]的區間

class Solution {
public:
    int divide(int A[], int begin, int end) {
        if (begin == end) return A[begin];
        if (begin + 1 == end)
            return max(max(A[begin], A[end]), A[begin] + A[end]);
        int mid = begin + (end - begin) /2;
        int lmax = divide(A, begin, mid - 1);
        int rmax = divide(A, mid + 1, end);
        int mmax = A[mid];
        int tmp = A[mid];
        for (int i = mid-1; i >= begin; --i) {
            tmp += A[i];
            if (tmp > mmax)
                mmax = tmp;
        }
        tmp = mmax;
        for (int i = mid+1; i <= end; ++i) {
            tmp += A[i];
            if (tmp > mmax) {
                mmax = tmp;
            }
        }
        return max(max(lmax, rmax), mmax);
    }
    int maxSubArray(int A[], int n) {
        return divide(A, 0, n-1);
    }
};

代碼轉自http://blog.csdn.net/xshengh/article/details/12708291