算法导论笔记 -- Step 5 [最大子数组]

**转载请注明**

第三章在讨论一些定义和理论，一些标记方法：
f(n) = O(g(n))  is like  a<=b
f(n) = Ω(g(n))  is like a>=b
f(n) = Θ(g(n))  is like  a=b
f(n) = o(g(n))  is like  a
f(n) = ω(g(n))  is like  a>b

======================= 分割线 ===========================
继续算法

求最大字数组：（假如你有一次机会去买去卖股票，图形如下，找出能获得最大收益的卖出买入点）



原理：
    提到这个算法实际是为了验证divide-and-conquer这种概念。
    在price中引入了change。（即变化）
    随便在change数组之间找个中间点，假如为: mid。
   假设数组为 [low, high]。 最大子数组结果为 [i, j]（i>=low, j<=high)。那么我们找到mid后，只有三种情况：
    1. i , j 都小于 mid 
    2. i , j 都大于 mid
   3. i 小于 mid，j 大于 mid

    对于1，2，那就接着取新的mid。对于3，从mid向左，以mid为准，取连续的最大的子数组；以mid+1为准，向右取最大，加一起。

    比较1，2，3.

#include <iostream>

using namespace std;

// I think if there is a struct stores these int[3] will be the best.
// That would be: max subarr of left point ; right point ; max calculated values
// Anyway, this worked

int* FIND_MAX_CROSSING_SUBARRAY( int*, int, int, int ); // left point ; right point ; max value
int* FIND_MAXIMUM_SUBARRAY( int*, int, int ); // as well

int main(){
    int a[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int* subarr = new int[3];

    subarr = FIND_MAXIMUM_SUBARRAY(a, 0, sizeof(a)/sizeof(int)-1);

    for (int i = subarr[0]; i <= subarr[1]; i++){
        cout << a[i] << endl;
    }
    return 0;
}

int* FIND_MAX_CROSSING_SUBARRAY( int* array, int low, int mid, int high ){
    int max_left = INT_MIN, max_right = INT_MIN;
    int max_left_p = mid, max_right_p = mid+1;
    for( int i = mid, max = 0; i >= low; i-- ){
        max += array[i];
        if ( max_left < max ){
            max_left_p = i;
            max_left = max;
        }
    }

    for( int i = mid+1, max = 0; i <= high; i++){
        max += array[i];
        if ( max_right < max ){
            max_right_p = i;
            max_right = max;
        }
    }

    int* max_subarr = new int[3];
    max_subarr[0] = max_left_p;
    max_subarr[1] = max_right_p;
    max_subarr[2] = max_left + max_right;

    return max_subarr; // left point ; right point ; max value
}

int* FIND_MAXIMUM_SUBARRAY( int* array, int low, int high ){
    if ( low == high ){ // only one item in array then return this as the biggest
        int* max_subarr = new int[3];
        max_subarr[0] = low;
        max_subarr[1] = high;
        max_subarr[2] = array[low];
        return max_subarr;
    } else{
        int mid = (high-low)/2+low; // set mid point as floor of half high and low
        int *left = new int[3], *right = new int[3], *cross = new int[3];

        left = FIND_MAXIMUM_SUBARRAY(array, low, mid);
        right = FIND_MAXIMUM_SUBARRAY(array, mid+1, high);
        cross = FIND_MAX_CROSSING_SUBARRAY(array, low, mid, high);

        if ( left[2] > right[2] && left[2] > cross[2] ){
            return left;
        } else if ( right[2] > left[2] && right[2] > cross[2] ){
            return right;
        } else {
            return cross;
        }
    }
}

运行结果：



空间复杂度： // 跟归并一样 
    O（n）

时间复杂度：
    O（nlgn)