# Reach End of Array With Max Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reach-end-of-array-with-max-score)
Canonical: https://scaleengineer.com/dsa/problems/reach-end-of-array-with-max-score
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` of length `n`.

Your goal is to start at index `0` and reach index `n - 1`. You can only jump to indices **greater** than your current index.

The score for a jump from index `i` to index `j` is calculated as `(j - i) * nums[i]`.

Return the **maximum** possible **total score** by the time you reach the last index.

**Example 1:**

**Input:** nums = \[1,3,1,5\]

**Output:** 7

**Explanation:**

First, jump to index 1 and then jump to the last index. The final score is `1 * 1 + 2 * 3 = 7`.

**Example 2:**

**Input:** nums = \[4,3,1,3,2\]

**Output:** 16

**Explanation:**

Jump directly to the last index. The final score is `4 * 4 = 16`.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 105`

# Approaches
## Brute-Force Dynamic Programming
This approach uses dynamic programming to solve the problem. We define `dp[i]` as the maximum score to reach index `i`. The base case is `dp[0] = 0`, as we start at index 0. To compute `dp[i]`, we consider all possible previous indices `j` (where `0 <= j < i`) from which we could have jumped to `i`. The total score for a path that ends with a jump from `j` to `i` is the maximum score to reach `j` (`dp[j]`) plus the score of the jump itself, which is `(i - j) * nums[j]`. We take the maximum over all possible `j` to find `dp[i]`. This leads to a straightforward nested loop implementation.
**Time:** O(n^2) - There are two nested loops. The outer loop runs `n` times, and the inner loop runs up to `n` times, leading to a quadratic time complexity. · **Space:** O(n) - We use a DP array of size `n` to store the maximum scores for each index.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller input sizes.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The recurrence relation for this dynamic programming approach is:

`dp[i] = max(dp[j] + (i - j) * nums[j])` for all `0 <= j < i`.

We can implement this by creating an array `dp` of size `n`. We initialize `dp[0] = 0` and then iterate from `i = 1` to `n-1`. For each `i`, we have an inner loop that iterates from `j = 0` to `i-1`, calculating the potential score from each `j` and updating `dp[i]` if a better path is found. We use `long` for score calculation to avoid overflow, as the scores can become large.

```java
import java.util.Arrays;

class Solution {
    public long maxScore(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        long[] dp = new long[n];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long currentScore = dp[j] + (long)(i - j) * nums[j];
                if (currentScore > dp[i]) {
                    dp[i] = currentScore;
                }
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
*   Create a `dp` array of size `n`, where `dp[i]` will store the maximum score to reach index `i`.
*   Initialize `dp[0]` to 0, as we start at index 0 with no score. Initialize all other `dp` values to a very small number.
*   Iterate with a variable `i` from 1 to `n-1` to compute `dp[i]` for each index.
*   Inside this loop, iterate with a variable `j` from 0 to `i-1`. This inner loop considers all possible previous indices `j` from which we can jump to `i`.
*   For each pair `(j, i)`, calculate the score of jumping from `j` to `i` and add it to the maximum score to reach `j`. The formula is `dp[j] + (long)(i - j) * nums[j]`.
*   Update `dp[i]` with the maximum score found among all possible `j`'s: `dp[i] = max(dp[i], dp[j] + (long)(i - j) * nums[j])`.
*   After the loops complete, `dp[n-1]` will hold the maximum score to reach the final index.
*   Return `dp[n-1]`.

## DP with Convex Hull Trick (Li Chao Tree)
The `O(n^2)` DP approach can be optimized by re-examining the recurrence relation. By rearranging the terms, we can see that calculating `dp[i]` is equivalent to finding the maximum value among a set of linear functions. Specifically, for each previous index `j`, we can define a line `y = nums[j] * x + (dp[j] - j * nums[j])`. Then, `dp[i]` is the maximum `y` value obtained by evaluating all lines `L_j` (for `j < i`) at `x = i`.

This problem of maintaining a set of lines and querying for the maximum value at a point is known as the Convex Hull Trick. Since we are adding lines whose slopes (`nums[j]`) are not in a specific order, we need a dynamic version of this technique. A Li Chao Tree is a data structure that excels at this, allowing both line insertions and point queries in logarithmic time.
**Time:** O(n log n) - The main loop runs `n` times. Inside the loop, both the query and add operations on the Li Chao Tree take `O(log n)` time. · **Space:** O(n) - We use a `dp` array of size `n`. The Li Chao Tree also requires `O(n)` space for its nodes.
**Pros:** Highly efficient, with a time complexity that passes the given constraints.; It's a general technique applicable to a range of DP optimization problems.
**Cons:** The implementation of a Li Chao Tree is complex and non-trivial.; Requires understanding of computational geometry concepts (Convex Hull Trick).
### Explanation
A Li Chao Tree is a segment tree where each node stores a single line that represents the upper envelope for some part of that node's range. When we add a new line, it's propagated down the tree, potentially replacing the line in some nodes if it's better. A query for a point `x` involves traversing from the root to the leaf corresponding to `x`, taking the maximum of the lines stored in the nodes along this path.

Both adding a line and querying for a point take `O(log C)` time, where `C` is the size of the coordinate space. In our case, `C = n`.

Here is the high-level structure of the solution using a Li Chao Tree:

```java
class Solution {
    // Represents a line y = mx + c
    static class Line {
        long m, c;
        public Line(long m, long c) {
            this.m = m;
            this.c = c;
        }
        public long eval(long x) {
            return m * x + c;
        }
    }

    // Placeholder for Li Chao Tree implementation
    static class LiChaoTree {
        // ... implementation details ...
        // public void addLine(Line line) { ... }
        // public long query(int x) { ... }
    }

    public long maxScore(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        // The actual Li Chao Tree would be initialized here.
        // For demonstration, we'll just show the logic.
        // LiChaoTree tree = new LiChaoTree(0, n - 1);

        long[] dp = new long[n];
        dp[0] = 0;

        Line firstLine = new Line(nums[0], 0);
        // tree.addLine(firstLine);

        for (int i = 1; i < n; i++) {
            // dp[i] = tree.query(i);
            // The following is a placeholder for the query result
            // In a real scenario, you would compute this with the tree.
            // For now, we re-calculate it naively to show the logic flow.
            long maxVal = Long.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                long val = (long)nums[j] * i + (dp[j] - (long)j * nums[j]);
                maxVal = Math.max(maxVal, val);
            }
            dp[i] = maxVal;

            Line newLine = new Line(nums[i], dp[i] - (long)i * nums[i]);
            // tree.addLine(newLine);
        }

        return dp[n - 1];
    }
}
```
*Note: A full Li Chao Tree implementation is quite involved and has been omitted for brevity. The key is understanding its role in optimizing the DP state transitions.*
### Algorithm
*   First, observe the DP recurrence: `dp[i] = max_{0 <= j < i} (dp[j] + (i - j) * nums[j])`.
*   Rearrange the expression inside the max: `dp[i] = max_{0 <= j < i} (nums[j] * i + (dp[j] - j * nums[j]))`.
*   This can be viewed as a computational geometry problem. For each `j`, we have a line `L_j(x) = m_j * x + c_j`, where the slope `m_j = nums[j]`, the y-intercept `c_j = dp[j] - j * nums[j]`, and we are querying for the maximum line value at `x = i`.
*   This is a classic Convex Hull Trick (CHT) problem. Since the slopes `m_j = nums[j]` are not added in monotonic order, and we need to perform point queries, a dynamic CHT data structure is required.
*   A Li Chao Tree is a suitable data structure for this. It's a segment tree built over the coordinate space (here, the indices `0` to `n-1`) that can efficiently handle adding lines and querying for the maximum value at a specific point.
*   The overall algorithm is:
    1.  Initialize `dp[0] = 0`.
    2.  Create a Li Chao Tree for the coordinate range `[0, n-1]`.
    3.  Create the first line `L_0` with `m = nums[0]` and `c = 0`, and add it to the tree.
    4.  Iterate `i` from 1 to `n-1`:
        a.  Query the Li Chao Tree at `x = i` to find the maximum score, which is `dp[i]`.
        b.  Create a new line `L_i` with `m = nums[i]` and `c = dp[i] - (long)i * nums[i]`.
        c.  Add this new line `L_i` to the Li Chao Tree.
    5.  Return `dp[n-1]`.

# Solutions
### Java

```java
class Solution {
public
  long findMaximumScore(List<Integer> nums) {
    long ans = 0;
    int mx = 0;
    for (int i = 0; i + 1 < nums.size(); ++i) {
      mx = Math.max(mx, nums.get(i));
      ans += mx;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long findMaximumScore(vector<int> &nums) {
    long long ans = 0;
    int mx = 0;
    for (int i = 0; i + 1 < nums.size(); ++i) {
      mx = max(mx, nums[i]);
      ans += mx;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMaximumScore(self, nums: List[int]) -> int: ans = mx = 0 for x in nums[: - 1]: mx = max(mx, x) ans += mx return ans

```