两种方法——
- 贪心思维,设
arr[i]
为以元素i结尾的子数组的最大和,那么arr[i] = max(arr[i-1]+nums[i], nums[i])
,最大的arr[i]
即是答案 - 分治思维,思路很简单,最大子数组和要么存在于左侧区间,要么存在于右侧区间,要么存在于跨越左右侧的区间
显然,贪心法的时间复杂度为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)); } };