单调队列 + 前缀和：连续子序列的最大和

逃离我推掉我的手 2023-10-06 19:43 33阅读 0赞

## 单调队列 + 前缀和：连续子序列的最大和 ##

#### 文章目录 ####

*  单调队列 + 前缀和：连续子序列的最大和
 *   *   *  单调队列
         *  问题：
         *  思路：
         *  代码：

#### 单调队列 ####

单调队列能在O(N)的时间内方便地维护一个长度为n的序列中,每个长度为m的区间的区间最值。单调队列是一个双端队列，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。单调递增队列内部元素始终为单调递增。同理单调递减队列内部始终为单调递减。而我们对单调队列进行的所有操作就是为了维护上述单调性质。  
  我们通过一个例子理解单调队列的运作方式：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
  队列为单调递增队列时，若当前元素大于队尾元素，则当前元素入队，队列保持单调递增。若当前元素小于队尾元素，则我们需要将队尾元素不断出队，直到新的队尾元素小于当前元素，再将当前元素入队，这样才能保证队列单调递增。  
  若当前遍历的是第i位元素，我们需要维护长度为m的子区间的最值，即队列中的元素必须在\[i - m + 1,i\]范围内，队首元素一定是队列中最早入队的元素，若队首元素不在此范围内，则将队首元素出队。  
  我们通过队尾的出入队来维持队列的单调性质，用队首的出队来维持队列中元素都处在某个子区间内，由于队列的单调性，队首元素一定是该子区间内的最小或最大值。

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 思路： ####

题目要我们在一个序列A中找到长度不超过m子区间，使这个子区间的和最大。对于求子区间的和的问题，我们可以使用前缀和数组`pre[]`，`[i,j]`子区间的和即为`pre[j] - pre[i - 1]`。若我们确定子区间的终点`j`，长度不超过`m`的子区间即为`[j - m + 1,j] ~ [j,j]`。而这些子区间中的最大和为多少呢，通过子区间和的公式可以看出，这些子区间中的最大和为`pre[j] - min(pre[j - m] ~ pre[j])`，则我们需要知道`pre[j - m] ~ pre[j]`中的最小值，此时单调队列就登场了，即我们需要维护一个保存长度为m + 1的区间内最小值的单调队列。  
  根据上述方法，我们可以求得确定右端点的子区间和的最大值，枚举每个元素为子区间的右端点，不断更新最大值即可  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**需注意的点**：  
  java中ArrayDeque和LinkedList类实现了双端队列Deque接口，分别提供了双端队列的数组和链表实现。Deque接口的几个常用的方法如下：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>void addFirst(E element)</td> 
   <td>将元素添加到队首</td> 
  </tr> 
  <tr> 
   <td>void addLast(E element)</td> 
   <td>将元素添加到队尾</td> 
  </tr> 
  <tr> 
   <td>E pollFirst()</td> 
   <td>队列不为空，删除并返回队头元素</td> 
  </tr> 
  <tr> 
   <td>E pollLast()</td> 
   <td>队列不为空，删除并返回队尾元素</td> 
  </tr> 
  <tr> 
   <td>E getFirst()</td> 
   <td>队列不为空，返回队头元素</td> 
  </tr> 
  <tr> 
   <td>E getLast()</td> 
   <td>队列不为空，返回队尾元素</td> 
  </tr> 
 </tbody> 
</table>

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static ArrayDeque<Integer> q = new ArrayDeque<>();
        static long[] pre = new long[300002];
        public static void main(String[] args) {
        
            int n, m, i;
            long ans = 0, num;
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            for (i = 1;i <= n;i++) {
        
                num = scanner.nextLong();
                pre[i] = pre[i - 1] + num;
                while (!q.isEmpty() && pre[q.getLast()] > pre[i]) {
        
                    q.pollLast();
                }
                q.addLast(i);
                if (q.getFirst() < i - m) {
        
                    q.pollFirst();
                }
                if (pre[i] - pre[q.getFirst()] > ans) {
        
                    ans = pre[i] - pre[q.getFirst()];
                }
            }
            System.out.println(ans);
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d8352b85abf94e9cabb1cac40323f28c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/39666e47c35d4664abeb20a5d904b64c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/b69a4a3cb8cc4f06bd33467522bab1e9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/de38950f89624d5b81e00a634d4e83ca.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16