#include <iostream>
#include <vector>
using namespace std;
/**
* 53, 最大子序列和
* 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: [4,-1,2,1] has the largest sum = 6.
*
* 求数组中的子数组的最大和
* 利用kadane 算法
*/
/**
* 方法 1,分治法来求解,二分搜索,
* 需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,
* 求出的最大值分别和左右两边得出的最大值相比较取最大的那一个
* */
int helper(vector<int> &nums, int left, int right)
{
if (left >= right)
return nums[left];
int mid = (left + right) >> 1;
int leftMax = helper(nums, left, mid - 1);
int rightMax = helper(nums, mid + 1, right);
int midMax = nums[mid], t = midMax;
for (int i = mid - 1; i >= left; i--)
{
t += nums[i];
midMax = max(midMax, t);
}
cout << t << " " << midMax << endl;
t = midMax;
for (int i = mid + 1; i <= right; i++)
{
t += nums[i];
midMax = max(midMax, t);
}
return max(midMax, max(leftMax, rightMax));
}
int maxSubArray1(vector<int> &nums)
{
if (nums.size() == 0)
return 0;
return helper(nums, 0, nums.size() - 1);
}
/**
* 方法 2,使用dp动态规划这个算法,推荐做法
* 1.设 f(i)f(i) 表示以第i个数字为结尾的最大连续子序列的总和是多少。
* 2.初始化 f(0)=nums[0]f(0)=nums[0]。
* 3.转移方程 f(i)=max(f(i−1)+nums[i], nums[i]);
* f(i)=max(f(i−1)+nums[i],nums[i])。可以理解为当前有两种决策,一种是将第i个数字和前边的数字拼接起来;
* 另一种是第i个数字单独作为一个新的子序列的开始。
* 4.最终答案为 ans=max(f(k)), 0≤k<nans=max(f(k)), 0≤k<n 。
*/
int maxSubArray(vector<int> &nums)
{
int n = nums.size();
vector<int> f(n);
f[0] = nums[0];
int maxNum = nums[0];
for (int i = 1; i < n; i++)
{
f[i] = max(f[i - 1] + nums[i], nums[i]);
maxNum = max(f[i], maxNum);
}
return maxNum;
}