邯郸网站seo,平台推广方案模板,网站开发并发 性能,创意设计文案审题#xff1a; 本题需要我们找到区间的最大子段和并输出结果 思路#xff1a; 方法一#xff1a;分治思想 我们可以把给定区间平均分成两部分#xff0c;然后获取左段区间的最大子段和#xff0c;右段区间的最大子段和#xff0c;以及跨区间的最大子段和。最后比较出他… 审题 本题需要我们找到区间的最大子段和并输出结果 思路 方法一分治思想 我们可以把给定区间平均分成两部分然后获取左段区间的最大子段和右段区间的最大子段和以及跨区间的最大子段和。最后比较出他们三种情况的最大子段和并返回 对于获取左右两段区间的最大子段和我们可以直接递归调用dfs进行对于最后一种情况则需要直接处理 处理方法 跨区间子段一定包含mid和mid1索引的值 对于mid我们往左遍历查找包含mid的连续左段的最大和 对于mid1:同理往右查找 最终我们把左段最大的值和右段最大的值加起来就是跨区间最大值 解题 #includeiostream
#includealgorithm
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[mid1]; int rmax a[mid1];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 最大子段和 - 洛谷
