幸运子序列

[编程题]幸运子序列

热度指数：816 时间限制：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

输出

算法知识视频讲解

xtims

针对每一个数，将其看作某连续子序列的次大值，这样就搜索了所有的可能性。找到最近的前后两个比其大的数作为最大值，求异或值。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> num;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int tmp;
        cin>>tmp;
        num.push_back(tmp);
    }
    int res = 0;
    for(int i=0;i<n;++i)
    {
        for(int j=i-1;j>=0;--j)
        {
            //找到就break，因为num[i]作为次大值
            if(num[j] > num[i])
            {
                res = max(res,num[j]^num[i]);
                break;
            }
        }
        for(int j=i+1;j<n;++j)
        {
            if(num[j] > num[i])
            {
                res = max(res,num[j]^num[i]);
                break;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

编辑于 2019-08-27 22:00:38 回复(4)

xxLilyxxZ

#include <iostream>
(720)#include <stack>
#include <vector>
using namespace std;
stack<int> stk;
int LuckyOne(vector<int>& data,int n){
	int len=n;
	int maxv=0,tmp;
	for(int i=0;i<n;i++){
		if(stk.empty())
			stk.push(data[i]);
		else{
			int top;
			while(!stk.empty()&&(top=stk.top())){
				tmp=top^data[i];
				if(maxv<tmp)
					maxv=tmp;
				if(top>data[i])
					break;
				else
					stk.pop();
			}
			stk.push(data[i]);
		}
	}
	return maxv;
}
int main(){
	int n;
	cin>>n;
	vector<int> data(n,0);
	for(int i=0;i<n;i++)
		cin>>data[i];
	cout<<LuckyOne(data,n)<<endl;
}

发表于 2020-03-03 11:13:09 回复(0)

Java

重洋

import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        int max=0;
        int temp;
        for(int i=0;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
                if(a[j]>=a[i])
                {
                    temp=a[i]^a[j];
                    max=max>temp?max:temp;
                    break;
                }
            for(int j=i+1;j<n;j++)
                if(a[j]>=a[i])
                {
                    temp=a[i]^a[j];
                    max=max>temp?max:temp;
                    break;
                }
        }
        System.out.println(max);
	}
	
}

发表于 2019-08-30 23:34:43 回复(0)

C/C++

面试好难呀

通过了80%，报错：运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。希望有人帮忙看看哪里错了

#include<iostream>

#include<vector>

using namespace std;

int getmax(vector<int> vec){
int res =0;
for(int i=1;i<vec.size()-1;i++){
int max1,max2,temp;
for(int j=i+1;j<vec.size();j++){
if(j==i+1){
if(vec[j]>vec[i]){
max1 = vec[j];
max2 = vec[i];
}else{
max1=vec[i];
max2=vec[j];
}
}else{
if(vec[j]>max1){
max2 = max1;
max1 = vec[j];
}else if(vec[j]>max2){
max2 = vec[j];
}else{
continue;
}
}
temp = max1^max2;
res = max(res,temp);
}
}
return res;
}

int main(){
vector<int> vec;
int temp;
while(cin>>temp){
vec.push_back(temp);
}
if(vec.size()<3|| vec[0]<2 ||vec[0]>100000)
return 0;
cout<<getmax(vec)<<endl;
return 0;
}

发表于 2019-08-27 20:40:22 回复(0)