幸运子序列

[编程题]幸运子序列

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

输出

算法知识视频讲解

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)

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)