首页 > 代码库 > POJ 2479 不相交最大子段和
POJ 2479 不相交最大子段和
题目意思还是很好理解的，在一个数列中，找出不相交的两个子串使得其和最大。
解题思路：
对于每个i来说，求出[0 ~ i - 1] 的最大子段和以及［i ~ n - 1］的最大子段和，在加起来，求最大的一个就行了。
［0 ~ i - 1］的最大子段和从左向右扫描，[i ~ n - 1] 的最大子段和从右向左扫描即可。时间复杂度为 O（n）
source code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))const int INF = 0x3f3f3f3f;int a[50001], left[50001], right[50001];int main(){ int i, j, t, k, n, m; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i = 0; i < n; ++i) scanf("%d",&a[i]); left[0] = a[0]; for(i = 1; i < n; ++i){ if(left[i - 1] < 0) left[i] = a[i]; else left[i] = left[i - 1] + a[i]; } for(i = 1; i < n; ++i){ left[i] = Max(left[i - 1], left[i]); //Max segment sum } right[n - 1] = a[n - 1]; for(i = n - 2; i >= 0; --i){ if(right[i + 1] < 0) right[i] = a[i]; else right[i] = right[i + 1] + a[i]; } for(i = n - 2; i > 0; --i){ right[i] = Max(right[i + 1], right[i]); //Max segment sum } int MAX = -INF; for(i = 1; i < n; ++i){ MAX = Max(MAX, left[i - 1] + right[i]); } printf("%d\n",MAX); } return 0;}
POJ 2479 不相交最大子段和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。