POJ 2479 不相交最大子段和

题目意思还是很好理解的,在一个数列中,找出不相交的两个子串使得其和最大。

解题思路:

  对于每个i来说,求出[0 ~ i - 1] 的最大子段和以及[i ~ n - 1]的最大子段和,在加起来,求最大的一个就行了。

  [0 ~ i - 1]的最大子段和从左向右扫描,[i ~ n - 1] 的最大子段和从右向左扫描即可。时间复杂度为 O(n)

 

source code:

 

//#pragma comment(linker, "/STACK:16216") //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[51], left[51], right[51];
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;
}

 

更多相关文章
  • pojMaximum sum(poj 2479)
    Maximum sum Time Limit: 1MS   Memory Limit: 6
  • 题目链接:http://poj.org/problem?id=2479 思路分析:假设数组为A[1, 2, …, n],则问题需要求数组A[s1, s1+1, …, t1]中的最大连续子段和与A[s2, …. , t2]中的最大连续子段和的和最大: 该问题实质上可以转换为求数组的最大子段和问题,只要 ...
  • 求一个区间内连续两段不相交区间最大和. // File Name: 2479.cpp // Author: Missa_Chen // Created Time: 2013年06月22日 星期六 16时19分02秒 #include <iostream> #include <str ...
  • 题意:求一段序列的最大两段子段和.   解法:dp.用pre数组记录以i结尾的上一次求的最大x段子段和,那么对于最大x+1段子段和,dp[i] = max(dp[i - 1], pre[i - 1]) + a[i],
  • 题目链接:http://poj.org/problem?id=2593 思路分析:该问题为求给定由N个整数组成的序列,要求确定序列A的2个不相交子段,使这m个子段的最大连续子段和的和最大. 该问题与poj 2479相同,解法也一样:   代码如下: #include <cstdio> # ...
  • Musical ThemeTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://poj.org/problem?id=1743 Description A musical melody is represented as a sequence of
  • 多版本的POJ分类 - 流传最广的一种分类: - 初期: - 一.基本算法: - (1)枚举. (poj1753,poj2965) - (2)贪心(poj1328,poj2109,poj2586) - (3)递归和分治法. - (4)递推. - (5)构造法.(poj3295) - (6)模拟法.( ...
  • POJ 2826 An Easy Problem?! 計算幾何,叉積
    题意: 在墙上钉两块木板,问能装多少水.即两条线段所夹的中间开口向上的面积(到短板的水平线
一周排行
  • 1.os模块   os模块包装了不同操作系统的通用接口,使用户在不同操作系统下,可以使用相同的函数接口,返回相同结构的结果.   os.name:返回当前操作系统名称('posix', 'nt', 'os2', 'm
  • 在indexReader和indexSearch中,如果频繁的去打开索引或者关闭索引,对资源的消耗比较大.所以一般采用单利的模式进行对indexReader的打开. 在indexReader的开发情景中,例如在一个查
  • 这些天用vmware在做solaris下的oracle测试 ,solaris是安装好了 ,可是当我想把oracle传到solaris系统中去的时候 ,我发现没法传 ,因为没有光盘 ,只有想辦法通过samba或者ssh ...
  • ArrayList是Java中最常用的集合类型之一.它允许灵活添加多个null元素,重复的元素,并保持元素的插入顺序.在编码时我们经常会遇到那种必须从已建成的ArrayList中删除重复元素的要求.这篇文章将给出两种 ...
  • <?php header('Content-Type:text/html;charset=utf-8'); function encode_file_contents($filename) { $type=st ...
  • 今天在使用VS2013编译一个控制台应用程序时出现了:error LNK2026 模块对于 SAFESEH 映像是不安全的,按照以下步骤轻松解决了. 打开该项目的“属性页”对话框,然后单击“链接器”--“命令行”,将
  • 


    		    squid.3.3.4配置限制訪問域名
    1:允许用户访问某些域名,我测试环境只写了一个; [[email protected]
  • 今天海关部的EPSON LQ1600KIII+打印机需要打印海关报表,需要连打,但是机器无源无故的不能打印,每次都是打印一张后就连续进几张纸后就提示缺纸,郁闷只能自己查了, 1,首先看逻辑打印机设置, (没问题) 2
  • 


    		    HP DL580Gen8支持的操作系統
    hp 的DL580可以说是很经典的PC服务器了,无论是在大企业去IOE的大潮中,还是中小企 ...
  • create table t_ext_tab(id char(1),name char(6)) organization external( type oracle_loader default directory ...