Итак, на прошлой неделе я опубликовал проблему для регионалов ACM ICPC Юго-Восток здесь -> Алгоритм вычисления числа 1 для диапазона двоичных чисел . Это было довольно хорошо получено и все еще не было решено, поэтому я решил, почему бы не бросить еще один вопрос, который моя команда не могла решить.
Проблема.
Ваши друзья только что открыли новый бизнес, и вы хотите посмотреть, насколько хорошо у них дела. Бизнес работает уже несколько дней, и ваши друзья записывают свою чистую прибыль каждый день. Вы хотите получить наибольшую общую прибыль, которую ваши друзья получили за любой последовательный промежуток времени, по крайней мере, один день. Например, если прибыль ваших друзей выглядела так:
Day 1: -3
Day 2: 4
Day 3: 9
Day 4: -2
Day 5: -5
Day 6: 8
Их максимальная прибыль за любой промежуток времени будет 14, со 2-го дня до 6.
Input
На входе будет несколько тестовых случаев. Каждый тестовый пример начинается с целого числа N (1 <= N <= 250 000) в отдельной строке, указывающего количество дней. На каждой из следующих N строк будет одно целое число P (-100 <= P <= 100), указывающее прибыль за этот день. Дни указаны в порядке. Ввод закончится строкой с одним 0 </p>
выход
Для каждого теста выведите одно целое число, представляющее максимальную прибыль за любой непустой промежуток времени. Выведите каждое целое число на отдельной строке без пробелов. Не печатайте никаких строк доски между ответами.
Пример ввода
6
-3
4
9
-2
-5
8
2
-100
-19
0
Пример вывода
14
-19
Код для решения этой проблемы довольно прост, если вы не беспокоитесь об эффективности, но единственный способ, которым это было решено на конкурсе, был в O (n!), Что недопустимо. Я надеюсь, что переполнение стека может быть лучше
Удачи!
EDIT
Просто для того, чтобы держать это в актуальном состоянии, здесь завершен код, который решает эту проблему в 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;
}
}