CSES - HIIT Open 2018 - Results
Submission details
Task:Buy Low, Sell High
Sender:HIIT AND RUN
Submission time:2018-05-26 11:31:56
Language:Java
Status:READY
Result:
Test results
testverdicttime
#1--details
#2--details
#3--details
#4--details
#5--details
#6ACCEPTED0.22 sdetails
#7ACCEPTED0.23 sdetails
#8ACCEPTED0.23 sdetails
#9--details

Code

import java.util.Scanner;

public class A {
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int[] p = new int[n];
		for (int i=0; i<n; i++) {
			p[i] = s.nextInt();
		}
		
		int minStart = p[0];
		int maxProfitAnywhereBetween = 0;
		int[] l = new int[n];
		for (int i=0; i<n; i++) {
			minStart = Math.min(minStart, p[i]);
			int profitIfSellHere = p[i] - minStart;
			maxProfitAnywhereBetween = Math.max(maxProfitAnywhereBetween, profitIfSellHere);
			l[i] = maxProfitAnywhereBetween;
		}
		
		int maxEnd = p[n-1];
		maxProfitAnywhereBetween = 0; 
		int[] r = new int[n];
		for (int i=n-1; i>=0; i--) {
			maxEnd = Math.max(maxEnd, p[i]);
			int profitIfBuyHere = maxEnd - p[i];
			maxProfitAnywhereBetween = Math.max(maxProfitAnywhereBetween, profitIfBuyHere);
			r[i] = maxProfitAnywhereBetween;
		}
		
		long ans = 0;
		for (int i=0; i<n; i++) {
			ans = Math.max(ans, (long)l[i] + (long)r[i]);
		}
		
		System.out.println(ans);
		s.close();
	}
}

Test details

Test 1

Verdict:

input
500000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
0

user output
(empty)

Test 2

Verdict:

input
500000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
499999

user output
(empty)

Test 3

Verdict:

input
500000
500000 499999 499998 499997 49...

correct output
0

user output
(empty)

Test 4

Verdict:

input
500000
617752857 533265574 365848360 ...

correct output
1999980408

user output
(empty)

Test 5

Verdict:

input
500000
209620375 316066031 756114325 ...

correct output
1999992655

user output
(empty)

Test 6

Verdict: ACCEPTED

input
1
1

correct output
0

user output
0

Test 7

Verdict: ACCEPTED

input
2
1 1

correct output
0

user output
0

Test 8

Verdict: ACCEPTED

input
2
2 1

correct output
0

user output
0

Test 9

Verdict:

input
500000
1 1000000000 2 2 2 2 2 2 2 2 2...

correct output
1999999998

user output
(empty)