首页 > 试题广场 >

幸运子序列

[编程题]幸运子序列

热度指数：4910 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛得到一个长度为n的整数序列V,牛牛定义一段连续子序列的幸运值为这段子序列中最大值和次大值的异或值(次大值是严格的次大)。牛牛现在需要求出序列V的所有连续子序列中幸运值最大是多少。请你帮帮牛牛吧。

输入描述:

第一行一个整数n,即序列的长度。(2<= n <= 100000)
第二行n个数，依次表示这个序列每个数值V[i], (1 ≤ V[i] ≤ 10^8)且保证V[1]到V[n]中至少存在不同的两个值.

输出描述:

输出一个整数,即最大的幸运值

示例1

输入

5
5 2 1 4 3

输出

算法知识视频讲解

乔碧萝殿下

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int max = Integer.MIN_VALUE;
        for(int j = 0; j < n; j++) {
            // 标志每个节点都为次最大值
            int secondIndex = arr[j];
                         // 向前找 找出最大值
            int first = 0;
            int firstMax = 0;
            int index1 = j;
            while(index1 != 0) {
                if(arr[index1 - 1] > arr[j]) {
                    first = arr[index1 - 1]; 
                    break;// 如果找到了就退出循环
                }
                index1--;
            }
            firstMax = first ^ secondIndex;
            max = Math.max(max, firstMax);

            // 向后找 找出最大值
            int second = 0;
            int secondMax = 0;
            int index2 = j;
            while(index2 != arr.length - 1) {
                if(arr[index2 + 1] > arr[j]) {
                    second = arr[index2 + 1];
                    break;// 如果找到了就退出循环
                }
                index2++;
            }
            secondMax =second ^ secondIndex;
            max = Math.max(secondMax, max);
        }
        System.out.println(max);
        sc.close();
    }
}

发表于 2019-03-19 17:19:04 回复(0)

茶月猫

本回答单纯献给读不懂题目的小伙伴们看。因为题目描述，理解没到位，所以代码也写错了。

题目中说的连续子序列，不是指单调递增或者递减啥的，而是保持该序列相对位置不变，里面的从任意某点开始到任意某点，都可以称作为连续子序列。

测试样例分析：

5 2 1 4 3

其中子序列5,2求出来异或为7；子序列4,3求出来异或也为7。这两种情况是异或最大的了，所以最后输出是7.

发表于 2019-04-24 23:02:00 回复(1)

机械暴龙兽丶

// 将每一个当前数字当做次大，往前找第一个大于当前数字的数值计算异或1，
// 往后找第一个大于当前数字得数值计算异或2
// 比较两个异或大小输出最终的最大值
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
int n;
cin >> n;
int v[n];
for(int i = 0; i < n; ++i)
cin >> v[i];
int Max = 0;
for(int i = 0 ; i < n; ++i)
{
for(int j = i - 1; j >= 0; --j)
{
if(v[j] > v[i])
{
int temp = v[j]^v[i];
if(temp > Max)
Max = temp;
break;
}

}
for(int j = i + 1; j < n; ++j)
{
if(v[j] > v[i])
{
int temp = v[j]^v[i];
if(temp > Max)
Max = temp;
break;
}
}
}
cout << Max << endl;
return 0;
}

发表于 2019-05-07 20:26:22 回复(4)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, s=0, x;
    stack<int> S;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &x);
        while(!S.empty() && S.top()<=x){
            s = max(s, x^S.top());
            S.pop();
        }
        if(!S.empty())
            s = max(s, x^S.top());
        S.push(x);
    }
    printf("%d\n", s);
    return 0;
}

发表于 2020-10-14 09:05:54 回复(0)

Python

阿耀哥

必须吐槽一下出题人的语文水平，连续的子序列不解释清楚了，我还以为是数字连续了，结果是位置连续。害得我浪费了很多时间。

开始用到子串遍历，超时了。最后参考楼上的思路，分别向左右遍历，寻找第一个比他大的值，然后做异或。

n=int(input())
s=list(map(int,input().split()))
xor_list=0
for x in range(n):
    for y in range(x+1,n):  #向右循环遍历
        if s[y]>s[x]:
            xor_list=max(xor_list,s[y]^s[x])
            break
    for y in range(x-1,-1,-1): #向左循环遍历
        if s[y]>s[x]:
            xor_list=max(xor_list,s[y]^s[x])
            break
print(xor_list)

发表于 2020-02-05 16:27:24 回复(0)

Function201809101538815

看不懂题目，哎

发表于 2019-03-18 17:43:40 回复(3)

Python

嘿哈嘿

'''
## 列举出所有连续子序列，时间复杂度过大，O(n^2)，未通过
n = int(input())
inp = [int(x) for x in input().split()]
max_num = 0
for i in range(2,n+1) :
    for j in range(n-i+1) :
        temp_sublist = list(set(inp[j:j+i]))
        if len(temp_sublist) == 1:
            continue
        else :
            max_value = max(temp_sublist)
            temp_sublist.remove(max_value)
            submax_value = max(temp_sublist)
            temp = max_value ^ submax_value
            if temp > max_num:
                max_num = temp
print(max_num)
'''
## 将max_num和submax_num“互换”，不通过
n = int(input())
inp = [int(x) for x in input().split()]
max_luck_num = 0
for i in range(n):
    submax_num = inp[i]
    for j in range(i,-1,-1):
        if inp[j] > inp[i] :
            max_num = inp[j]
            temp = max_num ^ submax_num
            if temp > max_luck_num :
                max_luck_num = temp
            break
    for j in range(i+1,n):
        if inp[j] > inp[i] :
            max_num = inp[j]
            temp = max_num ^ submax_num
            if temp > max_luck_num :
                max_luck_num = temp
            break
print(max_luck_num)

编辑于 2019-02-16 17:27:01 回复(1)

元气の悟空

#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std;
int main(){
    int n,i,res=0,x;
    stack<int> s;
    for(scanf("%d",&n),i=0;i<n;i++){
        scanf("%d",&x);
        while(s.size()&&s.top()<=x)
            res=max(res,x^s.top()),s.pop();
        if(s.size()) res=max(res,x^s.top());
        s.push(x);
    }
    printf("%d\n",res);
}

编辑于 2017-11-28 22:39:34 回复(14)

自闭了201904090952484

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < n; i++){
            int x = sc.nextInt();
            // stack维持的是一个单调递减的栈，
            // 如果当前元素比栈顶大，则当前元素作为最大值向前组成子序列，次大值依次为出栈的栈顶元素
            while (!stack.isEmpty() && stack.peek() <= x){
                res = Math.max(res, x ^ stack.pop());
            }
            // 如果stack非空，此时栈顶元素大于当前元素x，
            // 当前元素为次大值，栈顶为最大值计算异或值
            if (!stack.isEmpty()){
                res = Math.max(res, x ^ stack.peek());
            }
            stack.push(x);
        }
        System.out.println(res);
    }
}

感觉到自己的渺小与大神的差距让人绝望

发表于 2019-06-13 15:47:46 回复(0)

Java

嘎嘎嘎~

import java.util.*;
public class try2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            Cal(sc);
        }
    }
    public static void Cal(Scanner sc) {
        int n = sc.nextInt();
        int[] V = new int[n];
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            V[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            int l=-1, r=-1;
            for (int x = i - 1; x >= 0; x--) {
                if (V[x] > V[i]) {
                    l = x;
                    break;
                }
            }
            for (int y = i + 1; y < n; y++) {
                if (V[y] > V[i]) {
                    r = y;
                    break;
                }
            }
                if (l!=-1) {
//                    System.out.println("l="+V[l]+" i="+V[i]);
                    arr.add(V[l]^V[i]);
                }
                if (r!=-1) {
//                    System.out.println("i="+V[i]+" r="+V[r]);
                    arr.add(V[i]^V[r]);
                }
        }
        Collections.sort(arr, (a, b) -> {
            return b - a;
        });
        Iterator<Integer> it = arr.iterator();
        if (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

发表于 2019-04-22 20:25:54 回复(0)

zzas

发表于 2019-04-11 10:57:30 回复(0)

yaozh

第一种方法，搜索所有的子串，并计算最大的，算法复杂度太大，未通过

n = int(input())
v = list(map(int, input().split()))
luck = []
for i in range(n):
    j = i
    arr = []
    maxluck = 0
    while j >= 0:
        arr.append(v[j])
        zuida = max(arr)
        if len(arr) == 1:
            luckzhi = zuida ^ zuida
        elif len(arr) > 1:
            arr1 = arr[:]
            arr1.remove(zuida)
            cida = max(arr1)
            luckzhi = zuida ^ cida
        if luckzhi > maxluck:
            maxluck = luckzhi
        luck.append(maxluck)
        j = j - 1
print(max(luck))

第二种方法：参考别人的思路，将每个元素当做次大值，找到每个元素左边第一个比它大的，异或，找到右边第一个比它大的，异或，取值较大的存入列表，最后再求列表的最大值

n = int(input())
v =[int(i) for i in input().split()]
luck = []
for i in range(len(v)):
    j = i
    zuida = v[i]
    while j >= 0:
        if v[j] > v[i]:
            zuida = v[j]
            res = zuida ^ v[i]
            break
        else:
            res = zuida ^ v[i]
        j = j - 1
    k = i
    cida = v[i]
    while k < len(v):
        if v[k] > v[i]:
            cida = v[k]
            res = max(res, cida ^ v[i])
            break
        else:
            res = max(res, cida ^ v[i])
        k = k + 1
    luck.append(res)
print(max(luck))

发表于 2019-03-24 20:09:53 回复(0)

羚羊在找内推

#include<bits/stdc++.h>
using namespace std;

int main()
{
std::ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int>nums(n,0);
int ret = 0;
int tmp;

for(int i = 0; i < n; i++)
{
cin >> tmp;
nums[i] = tmp;
}
for(int i = 1; i < n; i++)
{
int j = i - 1;
int bigCount = 0;
int maxVal = 0;
// 寻找i角标前面比i大的第一个数字(因为要构成带有nums[i]的连续序列)
while(j >= 0)
{
if(nums[j] > nums[i])// 假如找到了比当前位置大的就计算一次然后退出
{
ret = max(ret, (nums[j] ^ nums[i]));
break;
}else if(nums[j] > maxVal)
{
ret = max(ret, (nums[j] ^ nums[i]));
maxVal = nums[j];
}
j--;
}
}
cout << ret << endl;
return 0;
}

发表于 2019-03-01 22:55:13 回复(0)

fangqi_方其

## 单调栈做法
def getLuckNum2(arr,n):#单调减栈 遇到不符合的情况弹栈计算结果
    # 找到每个元素 左边第一个比它大的 右边第一个比它大的 计算两者异或 然后更新结果就好了 等于都不可以
    s = []
    ans = -(1<<31)
    for idx in range(n):
        while s and arr[s[-1]] <= arr[idx]:
            #median = s.pop()  #弹出最后一个 中心
            ans = max(ans,arr[s[-1]]^arr[idx])
            s.pop()
        if s:
            ans = max(ans,arr[s[-1]]^arr[idx])  #即使最后栈还有 已经计算进去了
        s.append(idx)    
    print(ans)
    
getLuckNum2(arr,n)

发表于 2019-02-19 16:06:44 回复(0)

兰偷荀令香

参考思路：https://blog.csdn.net/dlwsd_/article/details/84028664

遍历每一个点，将该点作为次大值，向前向后遍历比它大的值作为最大值计算异或值存储最大的异或值

n = int(input().strip())

n_lst = list(map(int, input().strip().split()))
max_value = -float('inf')
for i in range(len(n_lst)):
for j in range(i):
if n_lst[i - j - 1] > n_lst[i]:
max_value = max(max_value, n_lst[i - j - 1] ^ n_lst[i])
break
for j in range(1, len(n_lst) - i):
if n_lst[i + j] > n_lst[i]:
max_value = max(max_value, n_lst[i + j] ^ n_lst[i])
break
print(max_value)

发表于 2019-02-19 15:00:48 回复(1)

Java

成程晨

/*
思路：数组dp[i]记录以v[i]为最大值时，往两边走找次大值记为 max2，得到的最大的幸运值
如果在往两边走的过程中，遇到的数比v[i]大(即v[i]不可能为最大值了)，则寻找结束，break
如果在往两边走的过程中，遇到的数比max2小，则继续找
如果在往两边走的过程中，遇到的数比max2大且比v[i]小，则比较dp[i]与v[i] ^ max2,取大值
*/
import java.util.*;
public class Main{
private static int max = Integer.MIN_VALUE;
public static void main(String[] args){
try(Scanner in = new Scanner(System.in)){
int n = in.nextInt();
int[] v = new int[n];
for(int i = 0;i < n;i++){
v[i] = in.nextInt();
}
System.out.println(helper(v,n));
}
}
public static int helper(int[] v,int n){
int[] dp = new int[n];
for(int i = 0;i < n;i++){
int max1 = v[i];
if(i != 0 && v[i - 1] <= max1){
int max2 = v[i - 1];
dp[i] = Math.max(dp[i],max1 ^ max2);
for(int k = i - 2;k >= 0;k--){
if(v[k] <= max1){
if(v[k] > max2) {
dp[i] = Math.max(dp[i],max1 ^ v[k]);
max2 = v[k];
}
}else{
break;
}
}
}
if(i != n - 1 && v[i + 1] <= max1){
int max2 = v[i + 1];
dp[i] = Math.max(dp[i],max1 ^ max2);
for(int k = i + 1;k < n;k++){
if(v[k] <= max1){
if(v[k] > max2) {
dp[i] = Math.max(dp[i],max1 ^ v[k]);
max2 = v[k];
}
}else{
break;
}
}
}
}
Arrays.sort(dp);
return dp[dp.length - 1];
}
}
/*
思路：数组dp[i]记录以v[i]为最大值时，往两边走找次大值记为 max2，得到的最大的幸运值
如果在往两边走的过程中，遇到的数比v[i]大(即v[i]不可能为最大值了)，则寻找结束，break
如果在往两边走的过程中，遇到的数比max2小，则继续找
如果在往两边走的过程中，遇到的数比max2大且比v[i]小，则比较dp[i]与v[i] ^ max2,取大值
*/
import java.util.*;
public class Main{
private static int max = Integer.MIN_VALUE;
public static void main(String[] args){
try(Scanner in = new Scanner(System.in)){
int n = in.nextInt();
int[] v = new int[n];
for(int i = 0;i < n;i++){
v[i] = in.nextInt();
}
System.out.println(helper(v,n));
}
}
public static int helper(int[] v,int n){
int[] dp = new int[n];
for(int i = 0;i < n;i++){
int max1 = v[i];
if(i != 0 && v[i - 1] <= max1){
int max2 = v[i - 1];
dp[i] = Math.max(dp[i],max1 ^ max2);
for(int k = i - 2;k >= 0;k--){
if(v[k] <= max1){
if(v[k] > max2) {
dp[i] = Math.max(dp[i],max1 ^ v[k]);
max2 = v[k];
}
}else{
break;
}
}
}
if(i != n - 1 && v[i + 1] <= max1){
int max2 = v[i + 1];
dp[i] = Math.max(dp[i],max1 ^ max2);
for(int k = i + 1;k < n;k++){
if(v[k] <= max1){
if(v[k] > max2) {
dp[i] = Math.max(dp[i],max1 ^ v[k]);
max2 = v[k];
}
}else{
break;
}
}
}
}
Arrays.sort(dp);
return dp[dp.length - 1];
}
}

发表于 2019-02-10 16:51:16 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strs = br.readLine().split(" ");
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = Integer.parseInt(strs[i]);
        }

        int res = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        //遍历所有元素作为子串最大值和次大值的情况
        for (int i = 0; i < n; i++) {
            //当前元素作为连续子序列(也即子串)的最大值的情况
            while (!stack.isEmpty() && stack.peek() <= v[i]) {
                res = Math.max(res, v[i] ^ stack.pop());
            }
            //当前元素作为连续子序列的次大值的情况
            if (!stack.isEmpty()) {
                res = Math.max(res, v[i] ^ stack.peek());
            }
            stack.push(v[i]);
        }
        System.out.println(res);
    }
}

发表于 2019-01-30 14:05:43 回复(0)

C/C++

TheAnswerstx

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;

int main()
{
int n;
cin>>n;
stack<long long> s;
long long res = 0;
for(int i=0;i<n;i++)
{
long long v;
cin>>v;
while(s.size()>0 && s.top()<=v)
{
res = max(res,v^s.top());
s.pop();
}
if(s.size()>0)
{ res = max(res,v^s.top()); }
s.push(v);
}
cout<<res<<endl;
return 0;
}

发表于 2019-01-29 11:02:17 回复(0)

燃烧的橙子

思路是三分搜索;

要得到l,r之间最大异或值，

先求出最大值，次大值下标index1，index2(假设index1<index2)。

然后求区间l,index2-1最大异或值，与区间ndex1+1,r的最大异或值，v[index1]^v[index2]，取三者最大值即可。

我觉得思路是这样，，但是代码写不出来，有好心人试试看，然后告诉我结果吗？

发表于 2017-11-28 21:07:28 回复(2)

提交观点

问题信息

贪心数组分治算法工程师爱奇艺 2018 排序

来自：爱奇艺2018秋季校招...

上传者：小小

难度：

19条回答 79收藏 8728浏览

通过挑战的用户

查看代码

陌生人mosh...

2022-08-28 17:31:16
前端学习中

2022-08-27 18:40:11
-173℃

2022-06-21 16:59:32
MC枫少

2022-06-16 15:30:20
大龄程序缘

2022-06-02 15:54:07

幸运子序列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题