最大子数组

两种方法——

1. 贪心思维，设arr[i]为以元素i结尾的子数组的最大和，那么arr[i] = max(arr[i-1]+nums[i], nums[i])，最大的arr[i]即是答案
2. 分治思维，思路很简单，最大子数组和要么存在于左侧区间，要么存在于右侧区间，要么存在于跨越左右侧的区间

显然，贪心法的时间复杂度为O(n)，分治法的时间复杂度为O(nlogn)

一直对“贪心”算法的概念比较模糊（或排斥），可能因为贪心这个词语不是那么正面吧，但这恰恰表明了贪心的核心：每一步都获取当前位置/状态下的最优值。联想到动态规划算法，不也是每一步都获取了当前的最优值吗？但贪心最后的解是每一步最优值中再取最优值（够贪心吧？），而动态规划直接取dp数组的最后一个值即可。

方法一：贪心

//
// Created by jt on 2020/9/3.
//
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int maxSubArray(int* A, int n) {
        // write code here
        int maxVal = A[0];
        for (int i = 1; i < n; ++i) {
            A[i] = max(A[i], A[i-1]+A[i]);
            maxVal = max(maxVal, A[i]);
        }
        return maxVal;
    }
};

方法二：分治

//
// Created by jt on 2020/9/3.
//
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int maxSubArray(int* A, int n) {
        // write code here
        return divideAndConquer(A, 0, n-1);
    }

private:
    int divideAndConquer(int *A, int left, int right) {
        if (left > right) return INT32_MIN;
        if (left == right) return A[left];
        int mid = left + (right-left)/2;
        int leftMax = divideAndConquer(A, left, mid);
        int rightMax = divideAndConquer(A, mid+1, right);
        int midMax = A[mid], tmp = A[mid];
        for (int i = mid - 1; i >= left; --i) {
            tmp += A[i];
            midMax = max(tmp, midMax);
        }
        tmp = midMax;
        for (int i = mid + 1; i <= right; ++i) {
            tmp += A[i];
            midMax = max(tmp, midMax);
        }
        return max(midMax, max(leftMax, rightMax));
    }
};