`
yzd
  • 浏览: 1809432 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

1888. Circular Sequence

 
阅读更多

TAG 贪心算法

设数组sum记录序列和,要找一个最大的子序列,只需找出 asc=max { sum[b]-sum[a] } 0<=a<b<=n,因为我们只需要找出一个最大值,所以不需要O(n^2),用pmin记录之前最小的sum[i],只需O(n)扫描一次即可。这样找到的子序列长度在1-n之间。

当然,还有一个问题要处理,序列接成一个圈。上面只求出一种情况,还有一种情况就是中间被舍弃,把首尾两段连接成子序列。我们只要仿照上面的方法,再求一个最小的子序列desc=min { sum[b]-sum[a] },然后用sum[n]减去desc便能得到asc。但这里注意desc的长度为1-n,总长度减去desc后的长度为 0-(n-1)。我们要去掉0的情况,补上n的情况。

但具体的处理方法见代码。//ps: 程序的&sum 居然被替换成求和符号,汗。。我加了个空格

分享到:
评论

相关推荐

    Dsp.zip_Fourier sequence_idft

    bi-linear Filter. Circular Convolution of two sequences using DFT and IDFT. Discrete Fourier Transform (DFT) of the sequence

    Fast Circular Cross Covariance:两个信号的Fast Circular Cross Covariance-matlab开发

    %% %[lags,cc]=CXCOV(a,b) 返回长度为 M-1 的圆形交叉协方差%sequence cc 具有相应的滞后。 %% % 圆形互协方差是归一化的圆形互相关函数% 去除均值的两个向量: % c(k) = sum[a(n)-mean(a))*conj(b(n+k)-mean(b))]/...

    计算机网络第六版答案

    Computer Networking: A Top-Down Approach, 6th Edition Solutions to Review Questions and Problems Version Date: May 2012 ...This document contains the solutions to review questions and problems for...

    php.ini-development

    ;;;;;;;;... 1.... 2.... 3.... 4.... 5.... 6.... The syntax of the file is extremely simple.... Section headers (e.g.... at runtime.... There is no name validation.... (e.g.... previously set variable or directive (e.g....

    VB编程资源大全(英文源码 表单)

    It must be in a sequence. There are many possible upgrades so you cannot Alt+Tab out etc. &lt;END&gt;&lt;br&gt;58,rotate.zip This example shows you how to create a circular form, and also track the mouse ...

    几种基本数据结构

    学数据结构的时候自己写的几种基本数据结构,包括binary tree,circular queueu,linked list,linked queue,linked stack,sequence list,sequence stack

    rfc全部文档离线下载rfc1-rfc8505

    rfc是网络协义的重要学习资源,为方便大家查看,特收藏整理如下。下面是其中一篇内容: Network Working Group Steve Crocker Request for Comments: 1 UCLA 7 April 1969 ... Network Working Group Request ...

    数据结构_费布拉契数列

    Fibonacci sequence of k order Note the capacity of the circular queue is k 数据结构参考资料

    LeetCode最全代码

    ...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...

    微软内部资料-SQL性能优化3

    Contents Overview 1 Lesson 1: Concepts – Locks and Lock Manager 3 Lesson 2: Concepts – Batch and Transaction 31 Lesson 3: Concepts – Locks and Applications 51 Lesson 4: Information Collection and ...

    CCS-model-for-ONT:一种新颖的流水线,可从一个分子读数中获得高精度序列

    Similar to the CCS(the Circular Consensus Sequence) model of PacBio It's including two step 1: Amplification : Here we descibed a novel technology: 'self-amplification' which is simple and quick. 2:...

    Applications of Classical Physics

    circular apertures 7.5 Fourier Optics: coherent illumination; point spread functions; Abb6 theory; phase contrast microscopy; Gaussian beams 7.6 Diffraction at a Caustic 8. Interference 8.1 ...

    大维随机矩阵的谱分析理论

    In the biological sciences, a DNA sequence can be as long as several billion trands. In financial research, the number of different stocks can be as large as tens of thousands In wireless ...

    史上最全的ios开发源码

    动画之Animation Sequence 动画之Genie Effect 动画之Steam View 分段选择类 分段选择(Segment)之URBSegmentedControl 分段选择类--SVSegmentedControl 扩展 分段选择之AKSegmentedControl 分段选择之Color Bar ...

Global site tag (gtag.js) - Google Analytics