这个使用动态规划是比较好理解的，但是这个分治法对我这种脑子不好使的来说真是难懂，现在搞懂了，记录一下。
// LeetCode53.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <vector> using namespace std; /* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 */ //动态规划的方法解的 //class Solution { //public: // int maxSubArray(vector<int>& nums) { // if (nums.empty()) return 0; // if (nums.size() == 1) return nums[0]; // int start = -1, end = -1, maxNum = nums[0], sumNum = nums[0]; // if (nums[0] > 0) // { // start = 0; // } // for (size_t i = 1; i < nums.size(); i++) // { // if (start == -1 && nums[i] <= 0) // { // if (maxNum < nums[i]) // { // start = end = i; // maxNum = sumNum = nums[i]; // } // continue; // } // if (start == -1 && nums[i] > 0) // { // start = i; // end = i; // sumNum = maxNum = nums[i]; // continue; // } // if (sumNum < 0 && nums[i] >= 0 && nums[i] >= maxNum) // { // start = i; // end = i; // sumNum = maxNum = nums[i]; // continue; // } // sumNum += nums[i]; // if (sumNum > maxNum) // { // maxNum = sumNum; // end = i; // } // } // return maxNum; // } //}; //官方分治法的解法，我资质驽钝真是不大好理解 #include <algorithm> //class Solution { //public: // int maxSubArray(vector<int>& nums) { // int pre = 0, maxAns = nums[0]; // for (auto &x : nums) // { // pre = max(pre + x, x); // maxAns = max(pre, maxAns); // } // return maxAns; // } //}; //class Solution { //public: // struct Status { // int lSum, rSum, mSum, iSum; // }; // // Status pushUp(Status l, Status r) // { // int iSum = l.iSum + r.iSum; // int lSum = max(l.lSum, l.iSum + r.lSum); // int rSum = max(r.rSum, r.iSum + l.rSum); // int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum); // Status st{ lSum, rSum, mSum, iSum }; // return st; // }; // // Status get(vector<int>& a, int l, int r) // { // Status st1 = { a[l], a[l], a[l], a[l] }; // if (l == r) return st1; // int m = (l + r) >> 1; // Status lSub = get(a, l, m); // Status rSub = get(a, m + 1, r); // return pushUp(lSub, rSub); // } // // int maxSubArray(vector<int>& nums) { // return get(nums, 0, nums.size() - 1).mSum; // } //}; //分治法，理解了默写一遍 class Solution { public: struct sumStatus { int lSum, rSum, maxSum, totalSum; }; sumStatus mergeSum(sumStatus left, sumStatus right) { int leftSum = max(left.totalSum + right.lSum, left.lSum); int rightSum = max(left.rSum + right.totalSum, right.rSum); int maxSum = max(max(left.maxSum, right.maxSum), left.rSum + right.lSum); int totalSum = left.totalSum + right.totalSum; sumStatus st = { leftSum, rightSum, maxSum, totalSum }; return st; } sumStatus getSum(vector<int>& nums, int left, int right) { sumStatus st = { nums[left], nums[left], nums[left], nums[left] }; if (left == right) { return st; } int middle = (left + right) / 2; sumStatus lsum = getSum(nums, left, middle); sumStatus rsum = getSum(nums, middle + 1, right); return mergeSum(lsum, rsum); } int maxSubArray(vector<int>& nums) { return getSum(nums, 0, nums.size() - 1).maxSum; } }; int main() { //vector<int> nums = { -2,1,-3,4,-1,2,1,-5,4 }; //vector<int> nums = { 1,-2,4,0}; vector<int> nums = { 1,-3,5,-4,2,3 }; Solution s; cout << s.maxSubArray(nums) << endl; }
