# Largest Element in an Array after Merge Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-element-in-an-array-after-merge-operations)
Canonical: https://scaleengineer.com/dsa/problems/largest-element-in-an-array-after-merge-operations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** array `nums` consisting of positive integers.

You can do the following operation on the array **any** number of times:

* Choose an integer `i` such that `0 <= i < nums.length - 1` and `nums[i] <= nums[i + 1]`. Replace the element `nums[i + 1]` with `nums[i] + nums[i + 1]` and delete the element `nums[i]` from the array.

Return _the value of the **largest** element that you can possibly obtain in the final array._

**Example 1:**

**Input:** nums = [2,3,7,9,3]
**Output:** 21
**Explanation:** We can apply the following operations on the array:
- Choose i = 0. The resulting array will be nums = [5,7,9,3].
- Choose i = 1. The resulting array will be nums = [5,16,3].
- Choose i = 0. The resulting array will be nums = [21,3].
The largest element in the final array is 21. It can be shown that we cannot obtain a larger element.

**Example 2:**

**Input:** nums = [5,3,3]
**Output:** 11
**Explanation:** We can do the following operations on the array:
- Choose i = 1. The resulting array will be nums = [5,6].
- Choose i = 0. The resulting array will be nums = [11].
There is only one element in the final array, which is 11.

**Constraints:**

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

# Approaches
## Brute-Force Recursion
This approach attempts to solve the problem by exploring every possible sequence of merge operations. It treats the problem as a search through a state space, where each state is a possible configuration of the array. From any given state, we can transition to new states by performing one of the currently valid merge operations. We can use recursion to explore all paths in this state space, eventually finding a final configuration that yields the largest possible element.
**Time:** Exponential, likely on the order of O(C^N) for some constant C, as the number of merge sequences can grow very rapidly with the size of the array N. This is far too slow for the given constraints. · **Space:** O(N * D), where N is the array size and D is the maximum recursion depth. In the worst case, the depth can be N, and each recursive call stores a new array, leading to very high, likely exponential, space usage.
**Pros:** It is a direct translation of the problem statement and explores all possibilities, guaranteeing the correct answer if it could run to completion.
**Cons:** Extremely inefficient and computationally expensive.; The number of possible states (different arrays) and sequences of merges grows exponentially, making it infeasible for the given constraints.; It will lead to a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
The core idea is to build a recursive function that simulates the process. For a given array, the function first checks for all possible merges. For each possible merge, it creates the resulting new array and calls itself recursively on this new array. If no merges are possible, it means we have reached a final state for that particular sequence of operations. We then find the largest element in this final array. The overall answer is the maximum of the largest elements found across all possible final states. Due to its exhaustive nature, this method guarantees finding the optimal solution, but its performance is prohibitive. A practical implementation would also require memoization to store results for previously seen array states to avoid re-computation, but the number of states is still too large.
### Algorithm
The brute-force approach explores all possible sequences of merge operations recursively.
1. Define a recursive function, say `findMax(array)`, that takes the current state of the array as input.
2. In the function, identify all possible valid merges. A merge at index `i` is valid if `0 <= i < array.length - 1` and `array[i] <= array[i+1]`.
3. If no valid merges are possible, the array is in a final state. The largest element in this final array is a candidate for the answer. We return this value.
4. If there are possible merges, iterate through each valid merge `i`:
    a. Create a new array by performing the merge operation at index `i`.
    b. Recursively call `findMax` with this new array.
    c. Keep track of the maximum value returned from all recursive calls.
5. The initial call would be `findMax(nums)`, and the function would explore the entire tree of possible merge sequences to find the global maximum element.

## Greedy Right-to-Left Scan
A highly efficient approach can be devised using a greedy strategy. The key insight is to process the array from right to left. By doing so, when we consider an element `nums[i]`, the element to its right (`nums[i+1]`, which might already be a sum of subsequent elements) has been made as large as possible. This maximizes our chances of being able to merge `nums[i]` and create an even larger number.
**Time:** O(N), where N is the number of elements in `nums`. This is because we iterate through the array exactly once. · **Space:** O(1), as we only use a few variables to store the running sum and loop index, regardless of the input array size.
**Pros:** Extremely efficient with linear time complexity.; Uses constant extra space.; Simple and concise to implement.
**Cons:** The correctness of the greedy strategy is not immediately obvious and relies on the insight that processing right-to-left and always merging when possible leads to an optimal result.
### Explanation
We can iterate from the end of the array towards the beginning. We'll maintain a running sum, let's call it `sum`, which represents the value of the rightmost element in the array we are currently forming. Initially, `sum` is just the last element, `nums[n-1]`. Then, for each element `nums[i]` from right to left, we check if `nums[i] <= sum`. If it is, we can perform the merge operation. It's always optimal to do so, as this creates a larger number, which in turn makes it more likely for the next element to its left to be mergeable. So, we update `sum` by adding `nums[i]` to it. If `nums[i] > sum`, a merge is not possible. This means `nums[i]` must form the beginning of a new element in the final array. We, therefore, reset `sum` to `nums[i]`. It can be proven that this process creates a sequence of final merged elements `S_1, S_2, ..., S_k` such that `S_1 > S_2 > ... > S_k`. The largest element is therefore `S_1`, which is the final value of our `sum` variable after the loop completes.

```java
class Solution {
    public long largestElementAfterMerge(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        long sum = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= sum) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
        }

        return sum;
    }
}
```
### Algorithm
The greedy algorithm processes the array from right to left in a single pass.
1. Initialize a variable `sum` (of type `long` to prevent overflow) with the value of the last element of the array, `nums[n-1]`.
2. Iterate through the array from the second-to-last element to the first (i.e., from `i = n-2` down to `0`).
3. In each iteration, compare the current element `nums[i]` with the current value of `sum`.
    a. If `nums[i] <= sum`, it means we can merge `nums[i]` with the block of elements to its right. We do this by adding `nums[i]` to `sum`: `sum = sum + nums[i]`.
    b. If `nums[i] > sum`, we cannot merge. This means `nums[i]` must start a new block. We reset `sum` to be `nums[i]`: `sum = nums[i]`.
4. After the loop finishes, the final value of `sum` will be the sum of the leftmost block of elements, which is proven to be the largest possible element in any final configuration.
5. Return the final `sum`.

# Solutions
### Java

```java
class Solution {
public
  long maxArrayValue(int[] nums) {
    int n = nums.length;
    long ans = nums[n - 1], t = nums[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] <= t) {
        t += nums[i];
      } else {
        t = nums[i];
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxArrayValue(vector<int> &nums) {
    int n = nums.size();
    long long ans = nums[n - 1], t = nums[n - 1];
    for (int i = n - 2; ~i; --i) {
      if (nums[i] <= t) {
        t += nums[i];
      } else {
        t = nums[i];
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxArrayValue(self, nums: List[int]) -> int: for i in range(len(nums) - 2, - 1, - 1): if nums[i] <= nums[i + 1]: nums[i] += nums[i + 1] return max(nums)

```