The Java Program: G_profits/profits.java
1 import java.io.*;
2 import java.util.*;
3
4 public class profits
5 {
6 public Scanner sc;
7 public PrintStream ps;
8
9
10
11
12
13 public void doit() throws Exception
14 {
15 sc = new Scanner( new File( "profits.judge" ) );
16 ps = new PrintStream( new FileOutputStream( "profits.out" ) );
17
18 for(;;)
19 {
20 int n = sc.nextInt();
21 if( n==0 ) break;
22
23 int best = -1000 * 100000;
24 int bestoverall = -1000 * 100000;
25
26 for( int i=0; i<n; i++ )
27 {
28 int daily = sc.nextInt();
29 best = Math.max( best+daily, daily );
30 if( best>bestoverall ) bestoverall = best;
31 }
32
33 ps.println( bestoverall );
34 System.out.println( bestoverall );
35
36 }
37 }
38
39
40
41
42
43 public void bruteforce() throws Exception
44 {
45 sc = new Scanner( new File( "profits.in" ) );
46 ps = new PrintStream( new FileOutputStream( "profits.out" ) );
47
48 int amounts[] = new int[1000000];
49
50 for(;;)
51 {
52 int n = sc.nextInt();
53 if( n==0 ) break;
54
55 for( int i=0; i<n; i++ )
56 {
57 amounts[i] = sc.nextInt();
58 }
59
60 int best = -1000*100000;
61 for( int i=0; i<n; i++ )
62 {
63 int sum = 0;
64 for( int j=i; j<n; j++ )
65 {
66 sum = amounts[j];
67 if( sum>best ) best = sum;
68 }
69 }
70
71 System.out.println( best );
72
73 }
74 }
75
76
77
78
79
80
81
82 public static void main( String[] args ) throws Exception
83 {
84 long start = System.currentTimeMillis();
85 new profits().doit();
86 long end = System.currentTimeMillis();
87 System.out.println( "Time: " + (end-start));
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 }