Като туристи, посещаващи нова за нас дестинация, имаме сложната задача, как за ограниченото ни време там, да посетим най-яките забележителности. Предварително сме проучили и сме съставили списък на забележителностите и техния рейтинг, но те са разпръснати из целия град, разстоянията помежду им са значителни и май ще можем да посетим само две от тях.
Създайте публичен клас TourGuide с метод
public static int getBestSightseeingPairScore(int[] places)който получава като аргумент масив от цели числа places и връща оценката на най-добрата двойка забележителности, която се изчислява по следния начин: places[i] е рейтингът на i-тата забележителност, а две забележителности i и j се намират на разстояние j - i една от друга. Оценката на двойката забележителности (i < j) се смята като places[i] + places[j] + i - j, т.е. сумата от рейтингите на двете забележителности, минус разстоянието помежду им.
| Извикване | Резултат |
|---|---|
getBestSightseeingPairScore(new int[]{8, 1, 5, 2, 6}) |
11 |
getBestSightseeingPairScore(new int[]{1, 2}) |
2 |
В първия пример по-горе, i = 0, j = 2, places[i] + places[j] + i - j = 8 + 5 + 0 - 2 = 11.
- Използването на структури от данни, различни от масив, не е позволено. Задачата трябва да се реши с помощта на знанията от първата лекция от курса.