Description#
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: The contiguous subarray [4,-1,2,1] has the largest sum = 6.
Follow-up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach.
Approach#
- Find the maximum element in the entire array. If it is not greater than 0, return that number directly.
- If the maximum element is greater than 0, then the maximum subarray sum must also be greater than 0. Traverse the array, if the number is positive, consider it as the start of a subarray and calculate the sum by adding subsequent positive numbers. If the sum becomes negative, start a new subarray. Update the maximum sum if a larger sum is found.
int maxSubArray(int* nums, int numsSize){
int now_val = 0,max_val = nums[0];
for(int i=0;i<numsSize;i++)//Find the maximum element
if(nums[i] > max_val)
max_val = nums[i];
if(max_val <= 0)//Return directly if the maximum element is not greater than zero
return max_val;
//Already confirmed that max_value is greater than zero
for(int i=0;i<numsSize-1;i++) {
if(nums[i] > 0) {
for(int j=i+1,now_val=nums[i];j<numsSize;j++) {
now_val += nums[j];
if(now_val <= 0)
break;
if(now_val > max_val)
max_val = now_val;
}
}
}
return max_val;
}