fork download
copy 
  1. import java.util.Scanner;
  2. class Main {
  3.     public static long max(long a, long b, long c) {
  4.         return Math.max(a, Math.max(b, c));
  5.     }
  6.  
  7.     public static long min(long a, long b, long c) {
  8.         return Math.min(a, Math.min(b, c));
  9.     }
  10.     // input : test cases 
  11.     // for each test case : number of operations (long val)
  12.     // make 2 dp arr max and min at each point since we have an op that converts neg to pos
  13.     // for each operation : operation type and integer value
  14.  
  15.     public static void main(String[] args) {
  16.         Scanner scanner = new Scanner(System.in);
  17.         int t = scanner.nextInt();
  18.         scanner.nextLine(); // Consume the newline character after reading 't'
  19.         while (t-- > 0) {
  20.             long b = scanner.nextLong();
  21.             scanner.nextLine(); // Consume the newline character after reading 'b'
  22.             long[] dp1 = new long[(int) (b + 1)];
  23.             long[] dp2= new long[(int) (b + 1)];
  24.             dp1[0]=1; // coz we start at one and min must be 1
  25.             dp2[0]=dp1[0]; // max anything.. even if all op reduce it then the dp1[0] is max
  26.             for (int i = 1; i <= b; i++) {
  27.                 String l = scanner.nextLine();
  28.                 char g = l.charAt(0);
  29.                 long e=0; // numerical value
  30.                 if(l.length()>2){
  31.                     // extract number after space
  32.                     e = Long.parseLong(l.substring(2));
  33.                 }
  34.                 // take the previous max and min from dp1 or 2 whichever helps to get max and min at this point
  35.                 //or just leave it if prev is better
  36.                 if (g == '+') {
  37.                     dp1[(int) i] = max(dp1[(int) (i - 1)] + e, dp2[(int) (i - 1)] + e, dp1[(int) (i - 1)]);
  38.                     dp2[(int) i] = min(dp1[(int) (i - 1)] + e, dp2[(int) (i - 1)] + e, dp2[(int) (i - 1)]);
  39.                 } else if (g == '-') {
  40.                     dp1[(int) i] = max(dp1[(int) (i - 1)] - e, dp2[(int) (i - 1)] - e, dp1[(int) (i - 1)]);
  41.                     dp2[(int) i] = min(dp1[(int) (i - 1)] - e, dp2[(int) (i - 1)] - e, dp2[(int) (i - 1)]);
  42.                 } else if (g == '*') {
  43.                     dp1[(int) i] = max(dp1[(int) (i - 1)] * e, dp2[(int) (i - 1)] * e, dp1[(int) (i - 1)]);
  44.                     dp2[(int) i] = min(dp1[(int) (i - 1)] * e, dp2[(int) (i - 1)] * e, dp2[(int) (i - 1)]);
  45.                 } else if (g == '/') {
  46.                     dp1[(int) i] = max(dp1[(int) (i - 1)] / e, dp2[(int) (i - 1)] / e, dp1[(int) (i - 1)]);
  47.                     dp2[(int) i] = min(dp1[(int) (i - 1)] / e, dp2[(int) (i - 1)] / e, dp2[(int) (i - 1)]);
  48.                 } else {
  49.                     dp1[(int) i] = max(-1 * dp1[(int) (i - 1)], -1 * dp2[(int) (i - 1)], dp1[(int) (i - 1)]);
  50.                     dp2[(int) i] = min(-1 * dp1[(int) (i - 1)], -1 * dp2[(int) (i - 1)], dp2[(int) (i - 1)]);
  51.                 }
  52.  
  53.             }
  54.         }
  55.         scanner.close();
  56.     }
  57. }
  58.  
Success #stdin #stdout 0.12s 54412KB
comments (?)
stdin
copy 
2
3
N
- 2
N
3
- 1
* 4
/ 2
stdout
copy 
Standard output is empty
https://ideone.com/SEA6q1
language:
Java (HotSpot 12)
created:
18 hours 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!