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];  // Ratings of contests
  12.  
  13.             // Read contest ratings
  14.             for (int i = 0; i < n; i++) {
  15.                 a[i] = scanner.nextInt();
  16.             }
  17.  
  18.             // Calculate and print the result for each test case
  19.             System.out.println(maximizeRating(n, a));
  20.         }
  21.  
  22.         scanner.close();
  23.     }
  24.  
  25.     private static int maximizeRating(int n, int[] a) {
  26.         // Step 1: Calculate initial rating x
  27.         int x = 0;
  28.         for (int i = 0; i < n; i++) {
  29.             if (a[i] > x) {
  30.                 x++;
  31.             } else if (a[i] < x) {
  32.                 x--;
  33.             }
  34.         }
  35.  
  36.         // Step 2: Calculate the gain array based on the contest ratings
  37.         int[] gain = new int[n];
  38.         for (int i = 0; i < n; i++) {
  39.             if (a[i] > x) {
  40.                 gain[i] = -1;  // Loss (if we consider this contest)
  41.             } else if (a[i] < x) {
  42.                 gain[i] = 1;   // Gain (if we consider this contest)
  43.             } else {
  44.                 gain[i] = 0;   // No change (if we consider this contest)
  45.             }
  46.         }
  47.  
  48.         // Step 3: Apply Kadane's algorithm to find the maximum subarray sum (optimal interval to skip)
  49.         int maxGain = 0;    // Max gain from skipping a subarray
  50.         int currentMax = 0; // Current sum while traversing the array
  51.  
  52.         for (int i = 0; i < n; i++) {
  53.             currentMax = Math.max(gain[i], currentMax + gain[i]); // Kadane's logic
  54.             maxGain = Math.max(maxGain, currentMax);  // Update the maximum gain
  55.         }
  56.  
  57.         // Step 4: Return the initial rating + the maximum gain from skipping an optimal subarray
  58.         return x + maxGain;
  59.     }
  60. }
  61.  
Success #stdin #stdout 0.12s 56544KB
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/kfF6Gq
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!