fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Cari panjang LIS dengan binary search (O(N log N))
  5. int lis_length(int *A, int n) {
  6.     int *tails = (int *)malloc(n * sizeof(int));
  7.     int len = 0;
  8.  
  9.     for (int i = 0; i < n; i++) {
  10.         // Binary search: cari posisi terkecil di tails yang >= A[i]
  11.         int lo = 0, hi = len;
  12.         while (lo < hi) {
  13.             int mid = (lo + hi) / 2;
  14.             if (tails[mid] < A[i])
  15.                 lo = mid + 1;
  16.             else
  17.                 hi = mid;
  18.         }
  19.         tails[lo] = A[i];
  20.         if (lo == len) len++;
  21.     }
  22.  
  23.     free(tails);
  24.     return len;
  25. }
  26.  
  27. int main() {
  28.     int n;
  29.     scanf("%d", &n);
  30.  
  31.     int *A = (int *)malloc(n * sizeof(int));
  32.     for (int i = 0; i < n; i++)
  33.         scanf("%d", &A[i]);
  34.  
  35.     int langkah = n - lis_length(A, n);
  36.     printf("%d\n", langkah);
  37.  
  38.     free(A);
  39.     return 0;
  40. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin 
5
1 3 2 5 4
stdout 
2
https://ideone.com/UFvXki
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

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!