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?! 計算幾何,叉積
    题意: 在墙上钉两块木板,问能装多少水.即两条线段所夹的中间开口向上的面积(到短板的水平线
一周排行
  • 


    		    編程樂趣:C#實現讀取12306余票信息
    C#实现的读取12306余票信息的,不需登录,直接使用Get方式的字符串请求即可. 原文链 ...
  • 


    		    多圖教程遷移您的信息到嶄新的@live.com/cn賬戶
    [email protected],而不少人已经开始使用他们所喜欢的新帐户.尽管
  • 乞讨A.B.C ∈[1.N] && A*B != C,d(A*B) == d(C)组的数量. 首先要知道d(x) = (x%9 == 0 ? 9 : x%9); 那么则会有A*B == C,则必有d( ...
  • 在做移动端时,当我们需要从服务器获得多个文件时,为了节约流量,服务器一般会返回一个压缩包,那我们就是下载完成后,在手机中进行解压到指定位置 SharpCompress就是可以在手机中进行解压一个类库(.net),在c
  • 写在前面 由于sharepoint服务器上的站点采用的域用户windows认证的方式登陆,而app项目虽然能够提供用户名和密码,但客户是不愿意在网络上这样传输的.所以给提供了使用ssl证书认证的方式.而webhttp
  • 由于SPRD的刷机工具ResearchDownload运行在window环境下:这样,我们平时在开发环境下编译出来的镜像文件就不能直接用于刷机了. 这里涉及到一个双系统中文件共享的方法.由于企业信息安全的原因,很多方
  • 


    		    載入SD卡圖片到Gallery與ImageSwitch使用詳解
    由于最近小马要使用下Gallery与ImageSwitch实现照片的预览功能,特此找个时间 ...
  • 


    		    (神州數碼)交換機配置文件備份,nos備份升級
    神州数码设备之交换机置文件备份,nos备份升级 1.配置TFTP服务器 这里我们使用Cis ...
  • from http://oldwiki.linux-vserver.org/Namespaces //开源不只是代码,还有思想 Namespaces You may have heard that alpha uti ...
  •     Concept        Header     Summary      Threads   <thread>  Standard, low-level, type-safe;     Fut ...