So, last week I posted a problem for the South East Regionals ACM ICPC here → Algorithm to calculate the 1s number for a range of numbers in binary format . This was pretty well received and has not yet been resolved, so I decided why not give up another question that my team could not solve.
Problem.
Your friends have just opened a new business, and you want to see how well they work. The business operates for several days, and your friends record their net profit every day. You want to find the highest total profit your friends have made in any period of time, at least one day. For example, if the profit of your friends looks like this:
Day 1: -3
Day 2: 4
Day 3: 9
Day 4: -2
Day 5: -5
Day 6: 8
Their maximum profit for any period will be 14, from 2 to 6 days.
Input
There will be several test cases at the input. Each test case starts with an integer N (1 <= N <= 250,000) on its own line indicating the number of days. Each of the next N lines will have one integer P (-100 <= P <= 100), which indicates profit for this day. Days are in order. Entry will be completed with a line with one 0
Output
For each test case, print a single integer representing the maximum profit for any non-empty period of time. Print each integer on a separate line with no spaces. Do not print any lines between answers.
Input example
6
-3
4
9
-2
-5
8
2
-100
-19
0
Output result
14
-19
, , , , O (n!), . ,
!
, , , O (n).
import java.util.Scanner;
public class Profits {
public static int seqStart=0, seqEnd=-1;
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
while (s.hasNextLine()) {
int current = s.nextInt();
if (current == 0)
break;
else {
int count = current;
int[] a = new int[count];
for (int x = 0; x < count; x++) {
a[x] = s.nextInt();
}
System.out.println(max_subarray(a));
}
}
}
private static int max_subarray(int[] a) {
int maxSum = a[0], thisSum = a[0];
for(int i=0, j=0;j<a.length;j++) {
thisSum = thisSum + a[j];
if(thisSum > maxSum) {
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if (thisSum < 0) {
i = j+1;
thisSum = 0;
}
}
return maxSum;
}
}