//最大子数组问题
/*
方法：动态规划
f(i) = a[i], i <0或f(i-1) <= 0;
f(i) = f(i-1) + a[i], i!=0, f(i-1) > 0
max(f[i]) 不太好想
*/
/*方法一：动态规划
sum代表了包含nums[i]时（以nums[i]结尾的子数组）的最大和
不断更新sum和res sum = max(sum + num, num)
分析：时间复杂度O（n）(线性)
*/
class Solution
{
public:
int maxSubArray(vector<int>& nums)
{
int res = INT_MIN, sum = 0;
for (int num : nums)
{
sum = max(sum + num, num);
res = max(res, sum);
}
return res;
}
//方法二：分治法
//具体过程：将数组分为左子数组、右子数组、跨越中点的子数组问题
//分析：时间复杂度O(nlgn)
//参考资料：《算法导论》
class Solution
{
public:
int maxSubArray(vector<int>& a)
{
return findMaxSubArray(a, 0, a.size()-1);//递归入口
}
//递归函数：找a[left...right]的最大子数组（归并排序和快速排序中也用到了分治法，可以类比一下）
int findMaxSubArray(vector<int>& a, int left, int right)//递归函数
{
if(right == left) return a[left];
int mid = (left+right)/2;
int left_sum = findMaxSubArray(a, left, mid);
int right_sum = findMaxSubArray(a, mid+1, right);
int cross_sum = findMaxCrossingSubArray(a, left, mid, right);
return max(max(left_sum, right_sum), cross_sum);
}
//找跨中点的最大子数组，我们只需找出形如A[i.. mid] 和A[mid+ 1. .j] 的最大子数组，然后将其合并即可。
int findMaxCrossingSubArray(vector<int>& a, int left, int mid, int right)
{
int left_sum,sum,right_sum;
sum = 0;
left_sum = a[mid];//初始化为参与计算的第一个元素
for(int i = mid; i>=left; i--)//从中间往左边遍历
{
sum += a[i];
if(sum>left_sum) left_sum = sum;
}
sum = 0;
right_sum = a[mid+1];//初始化
for(int j = mid+1; j<=right; j++) //从中间往右边遍历
{
sum += a[j];
if(sum>right_sum) right_sum = sum;
}
return (left_sum+right_sum);
}
};
