剑指offer（面试题42）：连续子数组的最大和

• 方法1：贪心算法

// 求数组中的所有子数组的最大和 
#include<iostream>
using namespace std;

bool isInputValid = true;

int findMaxSumOfSubArray(int * numbers, int length) {
    if(numbers == NULL || length <= 0) {
        isInputValid = false;
        return 0;
    }

    int nCurSum = 0;
    int nGreatestSum = 0;

    for(int i = 0; i < length; ++i) {
        if(nCurSum <= 0)
            nCurSum = numbers[i];
        else
            nCurSum += numbers[i];
        if(nCurSum > nGreatestSum)
            nGreatestSum = nCurSum;
    }
    return nGreatestSum;
}

• 方法2：动态规划

// 动态规划

int  findMaxSumOfSubArrayV2(int* numbers,  int length) {
    if(numbers == NULL || length <= 0) {
        isInputValid = false;
        return 0;
    }

    int * data = new int[length];

    data[0] = numbers[0];

    for(int i = 1; i < length; ++i) {
        if(data[i-1] <= 0)
            data[i] = numbers[i];
        else
            data[i] = data[i-1] + numbers[i];
    } 

    int max = data[0];
    for(int i = 1; i < length; ++i)
        if(data[i] > max)
            max = data[i];

    delete[] data;
    return max;
}

• 测试

int main() {
    int length = 6;
    int * data = new int[6];
    for(int i = 0; i < length; ++i) {
        if(i % 2 == 0)
            data[i] = 3 * i + 2;
        else
            data[i] = 2 * i - data[i-1];
        cout << data[i] << " "; 
    }
    cout << endl;
    cout << findMaxSumOfSubArray(data, length) << endl; 
    cout << findMaxSumOfSubArrayV2(data, length) << endl; 
    delete[] data;

}