Uva_Problems/Uva787.java at master · mostafamt/Uva_Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import java.util.*;
import java.io.*;
import java.math.BigInteger ;

// This algorithm runs : O(n) = n
// you can try another algorithm if you can't understand it
// for example , you can try O(n) = n^2 , may be accepted
// or you can try dynamic programming

public class Uva787 {

    public static final BigInteger zero = BigInteger.ZERO ;

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(System.in);
        PrintWriter pr = new PrintWriter(System.out);
        StringBuilder sb = new StringBuilder();

        while( in.ready() ){
            int x = 0 ;
            BigInteger ans = BigInteger.valueOf(0L);
            BigInteger sum = BigInteger.valueOf(0L);
            BigInteger first_negative = BigInteger.valueOf(0L);
            BigInteger last_negative = BigInteger.valueOf(0L);
            boolean negative_appeared = false , zero_appeared = false ;
            boolean first_num = true ;
            int len = 0 ;

            while( ( x = in.nextInt()) != -999999 ){
                if( x == 0 ){
                    // reset values
                    zero_appeared = true ;
                    if( sum.compareTo(zero) < 0 && len > 1 ){
                        BigInteger max = BigInteger.valueOf(0L);
                        if( first_negative.compareTo(last_negative) > 0 ){
                            max = first_negative ;
                        } else {
                            max = last_negative ;
                        }
                        if( max.compareTo(zero) != 0 ){
                            sum = sum.divide(max);
                        }
                    }
                    if( sum.compareTo(ans) > 0 ){
                        ans = sum ;
                    }
                    sum = zero ;
                    len = 0 ;
                    first_num = true ;
                    negative_appeared = false ;
                    first_negative = zero ;
                    last_negative = zero ;
                    continue;
                }

                if( first_num ){
                    sum = BigInteger.valueOf(x) ;
                    ans = sum ;
                    first_num = false ;
                } else {
                    sum = sum.multiply(BigInteger.valueOf(x));
                }

                if( sum.compareTo(ans) > 0 ){
                    ans = sum ;
                }

                if( x < 0 && negative_appeared ){
                    last_negative = BigInteger.valueOf(x) ;
                } else if( negative_appeared ){
                    last_negative = last_negative.multiply(BigInteger.valueOf(x));
                } else if( x < 0 ){
                    first_negative = sum ;
                    last_negative = BigInteger.valueOf(x);
                    negative_appeared = true ;
                }
                len++ ;
            }
            if( sum.compareTo(zero) < 0 && len > 1 ){
                BigInteger max = BigInteger.valueOf(0L);
                if( first_negative.compareTo(last_negative) > 0 ){
                    max = first_negative ;
                } else {
                    max = last_negative ;
                }
                if( max.compareTo(zero) != 0 ){
                    sum = sum.divide(max);
                }
            }
            if( sum.compareTo(ans) > 0 ){
                ans = sum ;
            }
            if( ans.compareTo(zero) < 0 && zero_appeared ){
                ans = zero ;
            }
            sb.append(ans).append('\n');
        }
        pr.print(sb.toString());
        pr.close();
        in.close();
    }

    static class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public boolean ready() throws IOException {return br.ready();}

        public void close() throws IOException { br.close(); }
    }
}