Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Main {
- public static void main(String[] args) {
- System.out.println("Hello World!");
- int[] arr = {1, 3, 4, 7, 6, 5, 4};
- System.out.println(maximizeJumpScore(arr)); //prints 36 as expected.
- //route: 1 -> 7 -> 6 -> 5 -> 4
- }
- public static int maximizeJumpScore(int[] arr) {
- Deque<int[]> stack = new ArrayDeque<>();
- int maxScore = 0;
- //int[] elem = {value, index, bestScore};
- for (int i = 0; i < arr.length; i++) {
- while (!stack.isEmpty() && stack.peek()[0] <= arr[i]) {
- stack.pop();
- }
- if (stack.isEmpty()) {
- maxScore = Math.max(maxScore, arr[i] * i);
- } else {
- maxScore = Math.max(maxScore, (i - stack.peek()[1]) * (arr[i]) + stack.peek()[2]);
- }
- stack.push(new int[]{arr[i], i, maxScore});
- }
- return maxScore;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement