算法题（169）：最大子段和（分治思想）

审题：

 本题需要我们找到区间的最大子段和并输出结果

思路：

方法一：分治思想

我们可以把给定区间平均分成两部分，然后获取左段区间的最大子段和，右段区间的最大子段和，以及跨区间的最大子段和。最后比较出他们三种情况的最大子段和并返回

对于获取左右两段区间的最大子段和，我们可以直接递归调用dfs进行，对于最后一种情况则需要直接处理

处理方法：

跨区间子段一定包含mid和mid+1索引的值

对于mid：我们往左遍历查找包含mid的连续左段的最大和

对于mid+1:同理往右查找

最终我们把左段最大的值和右段最大的值加起来就是跨区间最大值

解题：
 

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int dfs(int left, int right)
{if (left == right){return a[left];}int mid = (left + right) / 2;
//查找左右段最大子段和int ret = max(dfs(left, mid), dfs(mid + 1, right));//查找跨区间最大子段和int sum = a[mid]; int lmax = a[mid];for (int i = mid-1; i >= left; i--){sum += a[i];lmax = max(lmax, sum);}sum = a[mid+1]; int rmax = a[mid+1];for (int i = mid + 2; i <= right; i++){sum += a[i];rmax = max(rmax, sum);}ret = max(ret, lmax + rmax);return ret;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}cout << dfs(1, n) << endl;//返回区间1到n的最大子段和return 0;
}

P1115 最大子段和 - 洛谷