首页 > 试题广场 >

最长和谐连续子序列

[编程题]最长和谐连续子序列
  • 热度指数:1741 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
和谐连续序列是指一个连续序列中元素的最大值和最小值之间的差值正好是1。
现在,给定一个整数数组,你需要在所有可能的连续子序列中找到最长的和谐连续子序列的长度。

输入描述:
一行整数数组,由空格分割


输出描述:
一行一个数字表示答案,即最长和谐连续子序列的长度
示例1

输入

1 3 2 2 5 2 3 7

输出

3

说明

最长的连续和谐子序列是:[3,2,2]
示例2

输入

1 3 2 2 1 1 2 3

输出

5

说明

最长的连续和谐子序列是:[2,2,1,1,2]
1.穷举所有的连续子序列
2.用线性复杂度求取各个连续子序列的最大最小值
3.遇到和谐序列时更新和谐序列的最大长度
def judge(arr):
    # 使用O(n)的复杂度同时找出最大和最小值
    n = len(arr)
    if n <= 1:
        return False
    # 初始化最大最小值
    maximum, minimum = arr[0], arr[1]
    if maximum < minimum:
        maximum, minimum = minimum, maximum
    # 遍历数组更新最大和最小值
    for i in range(2, n):
        if arr[i] > maximum:
            maximum = arr[i]
        elif arr[i] < minimum:
            minimum = arr[i]
    return maximum - minimum == 1

if __name__ == "__main__":
    arr = list(map(int, input().strip().split()))
    n = len(arr)
    maxLen = 0
    # 遍历所有的连续子序列,如果满足和谐连续子序列的特征则更新长度
    for left in range(n):
        for right in range(left + 1, n + 1):
            if judge(arr[left: right]):
                maxLen = max(maxLen, right - left)
    print(maxLen)


编辑于 2021-01-19 13:04:58 回复(0)
a=input()
num=[int(n) for n in a.split()]
result=[0 for i in range(len(num))]
for i in range(len(num)):
    for j in range(i+1,len(num)):
        if (max(num[i:j+1])-min(num[i:j+1]))==1:
            result[i]=j-i+1
print(max(result))

发表于 2021-04-24 10:33:41 回复(0)

//滑动窗口
let arr = readline();
arr = arr.split(' ');
let maxLen=0, queue=[], curr=[];
arr.forEach(val => {
    queue[val]=queue[val] ? queue[val]+1 : 1;
    curr.push(val);

    let max=val, min=null;
    queue.forEach((v, index) => {
        if (min==null) min = index;
        if (max < index) max = index; 
    })

    while (max - min > 1 && curr.length>1) {
        let queueVal = curr.shift();
        if (queue[queueVal] == 1) delete queue[queueVal];
        else queue[queueVal]--;

       max=val, min=null;
        queue.forEach((v, index) => {
            if (min==null) min = index;
            if (max < index) max = index; 
        })
    }
    if (maxLen < curr.length && max-min==1) {
        maxLen = curr.length;
    }
})
console.log(maxLen);

发表于 2021-02-14 09:16:17 回复(0)
动态规划求解
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 判断序列是不是最长和谐连续子序列
    public static boolean is_result(int[] sub)
    {
        int min=sub[0],max=sub[0];
        for(int i=1;i<sub.length;i++)
        {
            if(min>sub[i])
                min=sub[i];
            if(max<sub[i])
                max=sub[i];
        }
        return max-min==1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] a= new int[99999];
        int[] dp= new int[99999];
        int k=0;
        while(in.hasNextInt())
        {
            a[k++]=in.nextInt();
        }
        dp[0]=0;
        for(int i=1;i<k;i++)
        {
            int min=a[i],max=a[i],len=1;
            for(int j=i-1;j>=0;j--)
            {
                if(is_result(Arrays.copyOfRange(a, j, i+1)))
                {
                    dp[i]=i+1-j;
                }
            }
            if(dp[i]<dp[i-1])
                dp[i]=dp[i-1];
        }
        System.out.println(dp[k-1]);
    }
}

发表于 2023-09-01 11:13:31 回复(0)
let arr=readline().split(' ').map(e=>Number(e))
let max=0
for(let i=0;i<arr.length-1;i++){
    if(i!=0&&arr[i]==arr[i-1]) continue
    let flag=-1
    let count=1
    for(let j=i+1;j<arr.length;j++){
        if(arr[i]==arr[j]){
            count++
        }
        else if(flag==-1&&Math.abs(arr[i]-arr[j])==1){
            count++
            flag=arr[i]>arr[j]?true:false
        }
        else if((flag==0&&arr[j]-arr[i]==1)||(flag==1&&arr[i]-arr[j]==1)){
            count++
        }
        else break
    }
    if(flag!=-1) max=Math.max(max,count)
}
console.log(arr.length==1?0:max)
js简单思路,对比自己之前的代码简洁也快了不少,还是有进步的
发表于 2022-08-03 22:15:44 回复(0)
从第二个数开始,遍历数组,每次都放入当前队列,同时找出当前队列的最大值与最小值
之后进行判断,只有两种情况才进行操作:
1. max-min>1,出队列,并重新计算最大值与最小值
2. max-min== 1 计算长度
//滑动窗口
const arr = readline().split(" ").map(item => parseInt(item))
const queue = []

if(arr.length <= 1) console.log(0)
else{
    let res = 0
    let min = arr[0], max = arr[0];
    queue.push(arr[0])
    for(let i = 1;i<arr.length;i++){
        queue.push(arr[i])
        if(arr[i]>max) max = arr[i]
        if(arr[i]<min) min = arr[i]
        while(max - min > 1){
            queue.shift();
            min = Math.min(...queue)
            max = Math.max(...queue)
        }
        if(max - min === 1){
            res = Math.max(res,queue.length)
        }
    }
    console.log(res)
}


发表于 2021-08-31 13:28:32 回复(0)
// 暴力解法
var str = readline()
var arr = str.split(' ')
var maxResult = 0
for(let i = 0;i<arr.length;i++) {
    for(let j = i+1;j<arr.length;j++) {
        let temp = arr.slice(i,j+1) // 由于slice的第二个参数不取到 j,因此想要取到 j 就要 j + 1
        let max = Math.max(...temp)
        let min = Math.min(...temp)
        if((max - min)==1&&(j-i+1)>maxResult){
           maxResult = j - i + 1
        } 
    }
}
print(maxResult)
发表于 2021-08-26 10:17:57 回复(0)
if len(A)==1:  #处理特例
    print(0)
else:          #非特例
    i=0
    j=0
    maxc=0
    while i<len(A):
        j=i
        t=[]
        tmin=A[j]
        tmax=A[j]
        while(tmax-tmin<=1 and j<len(A)  and abs(A[j]-tmin)<=1 and abs(A[j]-tmax)<=1):
            t.append(A[j])
            tmin=min(t)
            tmax=max(t)
            j=j+1
        c=len(t)
        if len(set(t))==1:
            c=0
        if c>maxc:
            maxc=c
        i=i+1
    print(maxc)

发表于 2021-05-18 19:16:03 回复(1)
from collections import deque
nums = list(map(int,input().split(' ')))
temp= deque()
len_max=0
def max_dis(temp):
    n_min=n_max=temp[0]
    for i in range(1,len(temp)):
        if temp[i]>n_max:n_max=temp[i]
        if temp[i]<n_min:n_min=temp[i]
    return n_max-n_min

for i in nums:
    temp.append(i)
    while temp and max_dis(temp)>1:
        temp.popleft()
    if temp and max_dis(temp)==1:
        if len(temp)>len_max:
            len_max=len(temp)
print(len_max)
发表于 2021-03-30 10:26:19 回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        int temValue=0,fir=0,maxLength=0,expectedValue=3;
        for(int i=1;i<s.length;++i){
            temValue=Integer.valueOf(s[i])-Integer.valueOf(s[i-1]);
            switch(temValue){
            case 0:
            break;
            case 1:
                if(expectedValue==3||expectedValue==1){
                    expectedValue=-1;
                }else{
                maxLength=maxLength>i-fir?maxLength:i-fir;
                fir=i-1;
                }
            break;
            case -1:
                if(expectedValue==3||expectedValue==-1){
                    expectedValue=1;
                }else{
                maxLength=maxLength>i-fir?maxLength:i-fir;
                fir=i-1;
                }
            break;
            default:
                if(expectedValue==1||expectedValue==-1){
                maxLength=maxLength>i-fir?maxLength:i-fir;
                if(maxLength==1)
                    maxLength=0;
                }
                fir=i;
                expectedValue=3;
                break;
        }
            if((expectedValue==1||expectedValue==-1)&&i==s.length-1)
                maxLength=maxLength>s.length-fir?maxLength:s.length-fir;
        }
        System.out.print(maxLength);
    
}
}
发表于 2021-03-05 22:36:15 回复(0)

js方法:倒序查看子序列是否满足,比较暴力

let _str =readline();
let _strArr = _str.split(' ');
    let _resultArr = [0];
    let _max = 0;
    for (let i = 0, len = _strArr.length - 1; i < len; i++) {
        _resultArr[i] = 0;
        for (let j = _strArr.length - 1; j > i; j--) {
            let _sliceArr = _strArr.slice(i, j + 1);
            if (Math.abs(Math.max.apply(null, _sliceArr) -
                    Math.min.apply(null, _sliceArr)) !== 1) {
                continue;
            } else {
                _resultArr[i] = (j - i + 1)>_resultArr[i]?(j - i + 1):_resultArr[i];
            }
        }
    }
    console.log(Math.max.apply(null, _resultArr));
发表于 2021-02-22 13:14:53 回复(0)
import java.io.*;
import java.util.*;
 
/**
 * @author:ljr
 * @date:2020-11-12 18:53
 */
public class Main {
    public static void main(String[] args) throws IOException {
 
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        int[] nums = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            nums[i] = Integer.valueOf(s[i]);
        }
 
        LinkedList<Integer> minL = new LinkedList<>();
        LinkedList<Integer> maxL = new LinkedList<>();
        int l = 0, r = 1;
        int len = 0, max = nums[0], min = nums[0];
        maxL.addLast(0);
        minL.addLast(0);
        int[] res = new int[]{-1, -1};
        while (r < nums.length) {
            while (!minL.isEmpty() && nums[minL.peekLast()] > nums[r]) {
                minL.removeLast();
            }
            minL.addLast(r);
            while (!maxL.isEmpty() && nums[maxL.peekLast()] < nums[r]) {
                maxL.removeLast();
            }
            maxL.addLast(r);
            max = nums[maxL.peekFirst()];
            min = nums[minL.peekFirst()];
            if (max - min < 2) {
                if (r - l + 1 > res[1] - res[0] + 1 && max != min) {
                    res[0] = l;
                    res[1] = r;
                }
            }
            while (max - min > 1) {
                if (l == minL.peekFirst()) {
                    minL.removeFirst();
                }
                if (l == maxL.peekFirst()) {
                    maxL.removeFirst();
                }
                max = nums[maxL.peekFirst()];
                min = nums[minL.peekFirst()];
                l++;
            }
            r++;
        }
        if (res[0] == -1) System.out.println(0);
        else
            System.out.println(res[1] - res[0] + 1);
    }
     
}
发表于 2021-01-17 14:50:46 回复(0)