Найти наибольшее возможное значение S(S=(min2∧min)), где min2 & min - наименьшее и следующее наименьшее целое число в k элементах массива

Question

Есть проблема программирования, над которой я работаю. Проблема как:

Дан массив A[] из N различных элементов. Пусть min2 и min наименьший и следующий наименьший элемент в интервале [L,R], где 1 ≤ L

S = (мин2 ∧мин).

где ∧ - побитовый оператор XOR. Я должен найти максимально возможное значение S.

Я написал 1 решение, которое находит максимально возможное значение для S, но его сложность высока. Я думал, можно ли это оптимизировать в любом случае. Поскольку даже диапазон k элементов не является фиксированным, я должен рассчитать для всех диапазонов, т.е. от k = 2 до длины массива. Подход, который я использую, заключается в том, чтобы сначала взять k как 2 и начать с 0-го элемента, найти min & min2 в первых k элементах, вычислить S, если он больше, чем предыдущий S, взяв это за S, иначе игнорируя его. После этого, начиная с 1-го элемента, я нахожу мин в следующих k элементах и ​​так далее. То же самое с другими более высокими диапазонами, то есть 3,4,5... Ниже приведен код, который я написал:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

    int num = 0, S = Integer.MIN_VALUE, min = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
    int[] input = null;

    try {
        BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferRead.readLine();
        num = Integer.parseInt(s);
        s = bufferRead.readLine();
        String arr[] = s.split(" ");

        input = new int[arr.length];
        for(int i =0; i<arr.length;i++) {
            input[i] = Integer.parseInt(arr[i]);
        }
    }
    catch(IOException e)
    {
        e.printStackTrace();
    }



    for(int k=2;k<=input.length;k++) {
         int j =0;

         while(j<input.length-k+1)
             {

             int i=j;

             for(i=j;i<(j+k);i++)
             {
             if(input[i] < min)
                 {
                 min2 = min;
                 min = input[i];
             }
                 else if(input[i] > min && input[i] < min2)
                 {
                 min2 = input[i];

             }


         }

         int st = (((min2 & min)^(min2 | min)) & (min2 ^ min));


         if(st > S)
             S = st;
            j++;
            min = Integer.MAX_VALUE;
            min2 = Integer.MAX_VALUE;
         }

        }
        System.out.println( S );

    }

}

Можно ли это как-то оптимизировать?

Answer 1

Это можно сделать с помощью линейного алгоритма O(N).

Чтобы упростить задачу, сделайте это для случая, когда второй наименьший элемент идет после наименьшего. Затем переверните массив и сделайте это снова (или просто обработайте массив в обратном порядке, начиная с последнего элемента).

Используйте каждый элемент массива как самый правый элемент интервала (A[R]). Теперь единственный элемент, который следует рассматривать как самый левый элемент интервала (A[L]) ближайший элемент меньше чем A[R] если есть. A[L], A[R] два наименьших элемента этого интервала, поэтому вычислить S для них и обновите результат при необходимости. И ближайший меньший элемент может быть найден с помощью стека.

Псевдо-код:

result = -infinity
for each X in array A:
    while NOT stack.empty AND stack.top > X: stack.pop
    if NOT stack.empty:
        result = max(result, X XOR stack.top)
    stack.push(X)
reverse array A and repeat

Доказательство: этот алгоритм (точнее, его первая половина) пробует каждый элемент массива как второй наименьший элемент некоторого интервала, так что (первый) наименьший элемент находится слева от него. Очевидно, это учитывает интервал A[L]..A[R], Также, если мы расширим этот интервал в любую сторону (или в обе стороны) и все дополнительные элементы этого расширенного интервала будут больше, чем A[R], затем A[R] по-прежнему является вторым наименьшим элементом, и этот интервал также учитывается алгоритмом (но он не меняет оптимальное значение S). Если хотя бы один дополнительный элемент меньше A[R] или вместо расширения мы начинаем сокращать интервал, A[R] больше не является вторым наименьшим элементом, поэтому такие интервалы не рассматриваются на этой конкретной итерации (но учитываются, когда мы пытаемся использовать какой-либо другой элемент как второй по величине или когда мы ожидаем первый по величине элемент справа от текущего элемента).