Ниже приведу задачу.
После очередного завершённого проекта программист Пётр решил переехать в деревню и заняться сельским хозяйством. Мелочиться он не стал, поэтому помимо домика в деревне сразу приобрёл несколько идущих подряд параллельных участков поля, расположенных вдоль прямой дороги. Участки были разделены заборами, при этом все заборы начинались от той самой дороги, но заканчивались на разном удалении от неё не доходя до противоположной границы участка.
Петру нужно объединить эти участки. Но так как Пётр перфекционист, он непременно хочет, чтобы получившийся объединённый участок:
1. был прямоугольным;
2. был ограничен дорогой и двумя уже имеющимися заборами (забор необязательно использовать целиком, а вот удлинять забор нельзя);
3. имел наибольшую возможную площадь.
Как и положено разработчику Пётр получает 300к/наносек, поэтому его совсем не беспокоит тот факт, что часть территории окажется неиспользованной.
Пётр хочет отдохнуть, поэтому он попросил вас помочь с нахождением площади такого участка.
Помогите Петру и найдите два забора, которые вместе с дорогой образуют максимальный по площади прямоугольный участок, и выведите эту площадь.
Ширина всех участков одинакова и равна 1.
На вход вашей программе подаётся одна строка, содержащая массив целых чисел length, где length[i] - длина i-ого забора. Иными словами i-ый элемент массива задаёт забор в виде отрезка от (i, 0) до (i, length[i]), где 0 - это дорога.
Причём 0≤length[i]≤10 000, а количество заборов n удовлетворяет условию 2≤n≤100 000.
Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются.
примеры:
Пример 1
Ввод:
2 4 3 2 1 4 1
Вывод:
16
В первом примере участок наибольшей площади образуется между двумя заборами длины 4.
Пример 2
Ввод:
1 2
Вывод:
1
В данном примере второй забор используется не на всю длину, т.к. нас интересуют только прямоугольные участки.
Мой код выглядит так:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String build = scanner.nextLine();
String[] list = build.split(" ");
int[] line = new int[list.length];
for (int i = 0; i < list.length; i++) {
line[i] = Integer.parseInt(list[i]);
}
int firtst = 0, second = 0, firtIndex = 0, secondIndex = 0;
for (int i = 0; i < line.length; i++) {
if (line[i] > firtst) {
second = firtst;
secondIndex = firtIndex;
firtst = line[i];
firtIndex = i;
} else if (line[i] > second) {
second = line[i];
secondIndex = i;
}
}
int result = (Integer.max(secondIndex,firtIndex) - Integer.min(secondIndex,firtIndex)) * Integer.min(firtst,second);
System.out.println(result);
}
}
удовлетворяет примеру, но решение конкретное не принимает, пишет - ответ не верный. Проблема состоит в том, что он ищет 2 максимума и считает площадь, но по условию нужно найти МАКСИМАЛЬНУЮ площадь. т.е на примере 4 5 4 алгоритм завалится и выдаст ответ - 4, хотя по факту - правильный ответ 8((2-0) * 4). как его доработать ?
