当前位置:网站首页>Hdu1231 maximum continuous subsequence (divide and conquer or dynamic gauge or double pointer)
Hdu1231 maximum continuous subsequence (divide and conquer or dynamic gauge or double pointer)
2022-07-05 07:17:00 【Woodenman Du】
Topic link
http://acm.hdu.edu.cn/showproblem.php?pid=1231
Question
Problem Description
Given K A sequence of integers { N1, N2, ..., NK }, Its arbitrary continuous subsequence can be expressed as { Ni, Ni+1, ...,
Nj }, among 1 <= i <= j <= K. The largest continuous subsequence is the largest sum of all the elements in the continuous subsequence ,
For example, given a sequence { -2, 11, -4, 13, -5, -2 }, The maximum continuous subsequence is { 11, -4, 13 }, Maximum and
by 20.
In this year's data structure examination paper , It is required to write the program to get the maximum and , Now add a request , That is, you also need to output the
The first and last elements of the subsequence .
Input
The test input contains several test cases , Each test case accounts for 2 That's ok , The first 1 Line gives a positive integer K( < 10000 ), The first 2 Line is given K It's an integer , Space between . When K by 0 when , End of input , The use case is not processed .
Output
For each test case , stay 1 Output the maximum sum in the line 、 The first and last elements of the maximal continuous subsequence
plain , Space between . If the largest continuous subsequence is not unique , Then the serial number is output i and j The youngest one ( As shown in the... Of the input sample 2、3 Group ). If all K Both elements are negative numbers , Then its maximum sum is defined as 0, Output the beginning and end elements of the whole sequence .
Solve
This question can be said to be very classic
Let's not talk about the practice of enumerating left and right by violence ,n^3 I can't get anywhere , Prefix and optimization is not a good practice .
Dynamic gauge
It is recommended to use Dynamic gauge 、 Or double pointer small simulation . But in fact, the idea is very simple
Describe the :
At first l and r All point to the starting point , then r turn right , At the same time, we calculate l To r And , If the sum is positive , that r Just go straight to the right , If less than or equal to 0, It shows that this addition is not the desired result ( And it's meaningless ), let l = r, Start adding again , Until the last number is added , During this period, the results of the maximum sum are constantly updated res
See the code later , I really can't explain this nonsense
Divide and conquer
I used to listen to data structures Divide and conquer It's the same question , Let me just talk about the train of thought , The code is gone :
The so-called divide and conquer is to constantly split a problem into multiple sub problems to deal with
For this question , Let's discuss first A state :
from l To r The maximum continuous sequence sum of , Nothing but exists in l To mid(mid = (l+r)/ 2) perhaps mid+1 To r In , Or include mid , There are... On the left and right , Then we need to take out the maximum continuous sequence sum of the three cases to take the maximum value
First look at There are... On the left and right The situation of , How can I ask , Directly from mid Spread to both sides separately to add , When will it stop , Can only be added to the boundary to stop .
Because adding a number and getting smaller does not mean that it will not become larger than before , So it can only be added continuously , Keep the maximum value
Look at the maximum continuous sequence and On both sides What about the situation ?
Divide and rule , Divide and rule , Then just split the sequence into two parts and continue the above process , When there is only one element left, it is the boundary , Less than 0 The number of has no additive meaning , Positive numbers can be added directly
Pseudo code Write about the , Because I never believe in my ability to describe :
int solve(int l, int r)
{
// When there is only one element
if(l == r){
if( This element < 0) return 0;
else return This element ;
}
int mid = (l + r) / 2;
// Left bound maximum
int left = solve(l, mid);
// The right bound is the largest
int right = solve(mid + 1, r);
// Including the middle bound
int l_num, r_num;
for mid to l
l_num = max(l_num, mid To l Elements and )
for mid to r
r_num = max(r_num, mid To r Elements and )
// Take the maximum value to return
return max(l_num + r_num, left, right);
}
AC Code
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 10000
using namespace std;
int n, a[N+1];
int main(void)
{
while(~scanf("%d", &n))
{
if(n == 0) break; // Run end judgment
bool ans = false; // Total negative number discrimination
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(a[i] >= 0) ans = true;
}
if(!ans){ // All negative numbers
cout <<0 <<" " <<a[1] <<" " <<a[n] <<endl;
continue;
}
// It turns out that
int l, r, resl, resr, res = -1e9, dp = 0;
l = r = resl = resr = 1;
for(int i = 1; i <= n; i++){
if(dp > 0){ // The sum of elements is greater than 0, Add elements directly
dp += a[i];
r++;
}else{ // The sum of elements is less than or equal to 0, Press 0 Additive elements
dp = a[i];
l = r = i; // Update the left and right boundaries
}
if(dp > res){
res = dp; // Update Max
resl = l; resr = r; // Update the left and right boundaries
}
}
cout <<res <<" " <<a[resl] <<" " <<a[resr] <<endl;
}
return 0;
}
边栏推荐
- GPIO port bit based on Cortex-M3 and M4 with operation macro definition (can be used for bus input and output, STM32, aducm4050, etc.)
- 二分查找(折半查找)
- Now there are HTML files and MVC made with vs (connected to the database). How can they be connected?
- Ros2 - first acquaintance with ros2 (I)
- 睿智的目标检测59——Pytorch Focal loss详解与在YoloV4当中的实现
- Concurrent programming - how to interrupt / stop a running thread?
- Steps and FAQs of connecting windows Navicat to Alibaba cloud server MySQL
- DelayQueue延迟队列的使用和场景
- 网易To B,柔外刚中
- 数学分析_笔记_第8章:重积分
猜你喜欢
程序中的负数存储及类型转换
Import CV2 prompt importerror: libgl so. 1: Cannot open shared object file: no such file or directory
Intelligent target detection 59 -- detailed explanation of pytoch focal loss and its implementation in yolov4
Do you choose pandas or SQL for the top 1 of data analysis in your mind?
U-Boot初始化及工作流程分析
数学分析_笔记_第8章:重积分
[idea] efficient plug-in save actions to improve your work efficiency
Anaconda navigator click open no response, can not start error prompt attributeerror: 'STR' object has no attribute 'get‘
Ros2 - configuration development environment (V)
Ros2 topic (VIII)
随机推荐
Netease to B, soft outside, hard in
SD_CMD_SEND_SHIFT_REGISTER
[OBS] x264 Code: "buffer_size“
PostMessage communication
The problem of configuring opencv in qt5.13.2 is solved in detail
SD_ CMD_ SEND_ SHIFT_ REGISTER
Ros2 - configuration development environment (V)
What is sodium hydroxide?
ROS2——功能包(六)
[software testing] 04 -- software testing and software development
DataGrid offline installation of database driver
GPIO port bit based on Cortex-M3 and M4 with operation macro definition (can be used for bus input and output, STM32, aducm4050, etc.)
SOC_SD_DATA_FSM
【无标题】
Do you choose pandas or SQL for the top 1 of data analysis in your mind?
Use of Pai platform
Binary search (half search)
能量守恒和打造能量缺口
Ros2 - workspace (V)
氢氧化钠是什么?