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?! 計算幾何,叉積
    题意: 在墙上钉两块木板,问能装多少水.即两条线段所夹的中间开口向上的面积(到短板的水平线
一周排行
  • 上一篇文章我们说到了ngx_http_limit_conn_module 模块,来限制并发连接数.那么请求数的限制该怎么做呢?这就需要通过ngx_http_limit_req_module 模块来实现,该模块可以通过
  • 


    		    java Memcache使用詳解
    Memcached-Java-Client是Memcached官方提供的Java语言访问M
  • 记录了HashMap也来看看Hashtable吧,最近打算换份实习,所以想看看书回顾一下,不然就快记不得了.....囧啊囧啊,记性太差怎么破??? Hashtable里面的一些变量: Entry<?,?> ...
  • jQuery1.9删除了一些在以前版本中已经过时的api,想要把那些不够安全的.缺乏效率的.用处不大的,以及带有误导的特性统统去掉.如果你想升级你的jquery版本,但又使用了如下被删除的api的话,可以引入Migr
  • 又见GCD Time Limit: 1/1 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1853 A
  • /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-col
  • Description You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color.
  • 官方的一个blog Final Release and Support Plan for the ArcGIS APIs / Viewers for Flex and Silverlight 网址: http://b
  • 通过VS2010的Package Manager Console安装的EF版本,会在项目根目录的packages目录中生成一个EntityFramework.4.3.0目录,安装什么版本就是什么版本的目录,直接删除该 ...
  • Problem Description 虽然不想,但是现实总归是现实,Lele始终没有逃过退学的命运,因为他没有拿到奖学金.现在等待他的,就是像FarmJohn一样的农田生涯.要种田得有田才行,Lele听说街上正在举