The Java Program: Profits.java

  1 /*
  2   SER 2010.  Problem G: Profits
  3   Author: Ryan Stansifer 
  4 */
  5 
  6 import java.io.*;
  7 import java.util.Scanner;
  8 
  9 /*
 10     Maximum contiguous subsequence sum of one or more elements.
 11 */
 12 public final class Profits {
 13 
 14    private static final Scanner STDIN =
 15       new Scanner (new BufferedInputStream (System.in));
 16 
 17    public static void main(String[] args) {
 18       for (;;) {
 19          final int n = STDIN.nextInt();
 20          if (n==0) break;
 21          int sum  = 0;
 22 
 23          // Non-empty subsequences mean the max could be negative
 24          int max = Integer.MIN_VALUE;
 25          for (int i=0; i<n; i++) {
 26             final int profit = STDIN.nextInt();
 27             assert -100 <= profit && profit <= 100;
 28             if (sum<0) sum=profit; else sum+=profit;
 29             assert -100 <= sum && sum <= 100*250000;
 30             if (sum>max) max = sum;
 31             assert -100 <= max && max <= 100*250000;
 32          }
 33          System.out.println (max);
 34       }
 35    }
 36 }