Advertisement
Guest User

Maximize Jump Score

a guest
Aug 14th, 2023
550
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.95 KB | Software | 0 0
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         System.out.println("Hello World!");
  4.         int[] arr = {1, 3, 4, 7, 6, 5, 4};
  5.         System.out.println(maximizeJumpScore(arr)); //prints 36 as expected.
  6.         //route: 1 -> 7 -> 6 -> 5 -> 4
  7.     }
  8.    
  9.     public static int maximizeJumpScore(int[] arr) {
  10.         Deque<int[]> stack = new ArrayDeque<>();
  11.         int maxScore = 0;
  12.         //int[] elem = {value, index, bestScore};
  13.         for (int i = 0; i < arr.length; i++) {
  14.             while (!stack.isEmpty() && stack.peek()[0] <= arr[i]) {
  15.                 stack.pop();
  16.             }
  17.             if (stack.isEmpty()) {
  18.                 maxScore = Math.max(maxScore, arr[i] * i);
  19.             } else {
  20.                 maxScore = Math.max(maxScore, (i - stack.peek()[1]) * (arr[i]) + stack.peek()[2]);
  21.             }
  22.             stack.push(new int[]{arr[i], i, maxScore});
  23.         }
  24.        
  25.         return maxScore;
  26.     }
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement