幸运子序列

[编程题]幸运子序列

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

输出

算法知识视频讲解

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)

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)