Description of the Problem
Find the contiguous sub-array within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
Solution1 (Brute Force)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int MaxInWhole = nums.at(0); // the max value in all the arries;
for (int i = 0; i < nums.size(); i++) {
int MaxInPart = nums.at(i); // the max value in arries begin from index i;
// for each i, set MaxInPart as nums[i];
int Sum = nums.at(i); // the sum added together begin from index i;
// for each i, set Sum as nums[i];
for (int j = i + 1; j < nums.size(); j++) {
Sum += nums.at(j); // accumulate Sum.
if (Sum > MaxInPart)
MaxInPart = Sum; // replace MaxInPart if Sum is larger.
}
if (MaxInPart > MaxInWhole)
MaxInWhole = MaxInPart; // replace MaxInWhole if MaxInPart is larger.
}
return MaxInWhole;
}
};
Time Limit Exceeded!
Leading to using divide and conquer.
Solution2(Divide and Conquer)
can't figure out myself, copied and learnt from https://leetcode.com/problems/maximum-subarray/discuss/
Largest_Sum(nums, i) = Largest_Sum(nums, i-1) > 0 ? Largest_Sum(nums, i-1) : 0 + nums[i];
if (Largest_Sum(nums, i - 1) > 0)
Largest_Sum(nums, i) = nums[i] + Largest_Sum(nums, i - 1);
else
Largest_Sum(nums, i) = nums[i];
