class Solution { public: int maxSubArray(vector& nums) { int pre = 0, maxAns = nums[0]; for (const auto &x: nums) { pre = max(pre + x, x); maxAns = max(maxAns, pre); } 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); return (Status) {lSum, rSum, mSum, iSum}; }; Status get(vector&a, int l, int r) { if (l == r) { return (Status) {a[l], a[l], a[l], a[l]}; } 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 & nums) { return get(nums, 0, nums.size() - 1).mSum; } };
难搞。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)