LeetCode第53題
題目描述：
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6绊袋。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
思路
采用分治法來做，時(shí)間復(fù)雜度會(huì)比較低铸鹰。將數(shù)組分為左子數(shù)組和右子數(shù)組癌别。那么最大子序就有三種存在位置：完全被包含于左子數(shù)組，完全被包含于右子數(shù)組蹋笼，跨越中點(diǎn)同時(shí)存在于左右兩個(gè)子數(shù)組中展姐。對(duì)于前兩種情況，可以遞歸求解剖毯。
對(duì)于最后一種情況圾笨，需要獨(dú)立考慮。因?yàn)楸厝豢缭街悬c(diǎn)逊谋，所以子序中必然包含中點(diǎn)擂达。所以從中點(diǎn)開始，分別向左向右搜尋最大的序列和胶滋。最后將左右最大序列號(hào)相加谍婉。
源代碼
int maxSubArray(int* nums, int numsSize){
return find_max_subarray(nums,0,numsSize - 1);
}
int find_max_subarray(int A[],int low,int high){
int mid,left_sum,right_sum,cross_sum;
if(low == high)
return A[low];
else{
int mid = (low + high) / 2;
left_sum = find_max_subarray(A,low,mid);
right_sum = find_max_subarray(A,mid + 1,high);
cross_sum = find_max_cross_subarray(A,low,mid,high);
}
if(left_sum >= right_sum && left_sum >= cross_sum)
return left_sum;
else if(right_sum >= left_sum && right_sum >= cross_sum)
return right_sum;
else
return cross_sum;
}
int find_max_cross_subarray(int A[],int low,int mid,int high){
int left_sum = A[mid];
int sum = 0;
for(int i = mid;i >= low;--i){
sum = sum + A[i];
if(sum > left_sum){
left_sum = sum;
}
}
int right_sum = A[mid + 1];
sum = 0;
for(int j = mid + 1;j <= high;++j){
sum = sum + A[j];
if(sum > right_sum){
right_sum = sum;
}
}
return (left_sum + right_sum);
}
分析
時(shí)間復(fù)雜度為O(nlgn)，空間復(fù)雜度為常數(shù)級(jí)別（不包含遞歸時(shí)所開辟函數(shù)的椂频觯空間）穗熬。
