fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args) {
  6.         Scanner scanner = new Scanner(System.in);
  7.         int t = scanner.nextInt(); // Number of test cases
  8.  
  9.         while (t-- > 0) {
  10.             int n = scanner.nextInt(); // Number of contests
  11.             int[] a = new int[n]; // Performance ratings in the contests
  12.  
  13.             // Read the array input
  14.             for (int i = 0; i < n; i++) {
  15.                 a[i] = scanner.nextInt();
  16.             }
  17.  
  18.             // Calculate and output the maximum possible rating
  19.             System.out.println(maximizeRating(n, a));
  20.         }
  21.  
  22.         scanner.close();
  23.     }
  24.  
  25.     // Function to calculate the maximum possible rating after skipping optimally
  26.     private static int maximizeRating(int n, int[] a) {
  27.         // Step 1: Calculate initial rating without any skips
  28.         int x = 0;
  29.         for (int i = 0; i < n; i++) {
  30.             if (a[i] > x) {
  31.                 x++;
  32.             } else if (a[i] < x) {
  33.                 x--;
  34.             }
  35.         }
  36.  
  37.         // Step 2: Use prefix sum difference to determine optimal gain from skipping
  38.         int[] gain = new int[n];
  39.         for (int i = 0; i < n; i++) {
  40.             if (a[i] > x) {
  41.                 gain[i] = -1; // Rating drop
  42.             } else if (a[i] < x) {
  43.                 gain[i] = 1;  // Rating increase
  44.             } else {
  45.                 gain[i] = 0;  // No change
  46.             }
  47.         }
  48.  
  49.         // Step 3: Apply Kadane's Algorithm to find maximum subarray sum
  50.         int maxGain = 0;
  51.         int currentMax = 0;
  52.         for (int i = 0; i < n; i++) {
  53.             currentMax = Math.max(gain[i], currentMax + gain[i]);
  54.             maxGain = Math.max(maxGain, currentMax);
  55.         }
  56.  
  57.         // Step 4: Return the initial rating + maximum gain found
  58.         return x + maxGain;
  59.     }
  60. }
  61.  
Success #stdin #stdout 0.12s 56224KB
comments (?)
stdin
copy 
5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10
stdout
copy 
11
8
1
4
4
https://ideone.com/AdVqW6
language:
Java (HotSpot 12)
created:
5 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!