審題：

?本題需要我們找到區間的最大子段和并輸出結果

思路：

方法一：分治思想

我們可以把給定區間平均分成兩部分，然后獲取左段區間的最大子段和，右段區間的最大子段和，以及跨區間的最大子段和。最后比較出他們三種情況的最大子段和并返回

對于獲取左右兩段區間的最大子段和，我們可以直接遞歸調用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 最大子段和 - 洛谷