fork(3) download 
  1. import java.util.Arrays;
  2.  
  3. public class Main
  4. {
  5. // A function to fund a sorted subsequence of size 3
  6. static void find4Numbers(int arr[], int n)
  7. {
  8.    int max = n-1; //Index of maximum element from right side
  9.    int min = 0, second = -1; //Index of minimum element from left side
  10.    int i;
  11.  
  12.    // Create an array that will store index of a smaller
  13.    // element on left side. If there is no smaller element
  14.    // on left side, then smaller[i] will be -1.
  15.    int[] smaller = new int[n];
  16.    int[] betweenSmallerAndCurrent = new int[n];
  17.    smaller[0] = -1;  // first entry will always be -1
  18.    betweenSmallerAndCurrent[0] = -1;
  19.    for (i = 1; i < n; i++)
  20.    {
  21.        if (arr[i] <= arr[min])
  22.        {
  23.           min = i;
  24.           smaller[i] = -1;
  25.           betweenSmallerAndCurrent[i] = -1;
  26.        }
  27.        else
  28.        {
  29.           smaller[i] = min;
  30.           if (second != -1 && arr[second] < arr[i])
  31.              betweenSmallerAndCurrent[i] = second;
  32.           else 
  33.              betweenSmallerAndCurrent[i] = -1;
  34.           if (second == -1 || arr[i] < arr[second])
  35.              second = i;
  36.        }
  37.    }
  38.  
  39.    // Create another array that will store index of a
  40.    // greater element on right side. If there is no greater
  41.    // element on right side, then greater[i] will be -1.
  42.    int[] greater = new int[n];
  43.    greater[n-1] = -1;  // last entry will always be -1
  44.    for (i = n-2; i >= 0; i--)
  45.    {
  46.        if (arr[i] >= arr[max])
  47.        {
  48.           max = i;
  49.           greater[i] = -1;
  50.        }
  51.        else
  52.           greater[i] = max;
  53.    }
  54.  
  55.    // make sure they're right
  56.    System.out.println(Arrays.toString(smaller));
  57.    System.out.println(Arrays.toString(betweenSmallerAndCurrent));
  58.    System.out.println(Arrays.toString(greater));
  59.  
  60.    // Now find a number which has both a greater number on
  61.    // right side and smaller number on left side
  62.    for (i = 0; i < n; i++)
  63.    {
  64.        if (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1)
  65.        {
  66.           System.out.printf("%d %d %d %d\n",
  67.                             arr[smaller[betweenSmallerAndCurrent[i]]],
  68.                             arr[betweenSmallerAndCurrent[i]],
  69.                             arr[i],
  70.                             arr[greater[i]]);
  71.           return;
  72.        }
  73.    }
  74.  
  75.    // If we reach number, then there are no such 3 numbers
  76.    System.out.println("No such triplet found");
  77. }
  78.  
  79.    public static void main(String[] args) throws Exception
  80.    {
  81.     int arr[] = {12, 11, 10, 5, 6, 2, 9, 30};
  82.     int n = arr.length;
  83.     find4Numbers(arr, n);
  84.    }
  85. }
  86.  
Success #stdin #stdout 0.07s 380224KB
comments ()
stdin 
Standard input is empty
stdout 
[-1, -1, -1, -1, 3, -1, 5, 5]
[-1, -1, -1, -1, -1, -1, 4, 4]
[7, 7, 7, 7, 7, 7, 7, -1]
5 6 9 30
https://ideone.com/DZDyBA
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!