2789. Largest Element in an Array after Merge Operations
Description
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 that0 <= i < nums.length - 1
andnums[i] <= nums[i + 1]
. Replace the elementnums[i + 1]
withnums[i] + nums[i + 1]
and delete the elementnums[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
Solutions
Solution 1: Merge in Reverse Order
According to the problem description, in order to maximize the maximum element in the merged array, we should merge the elements on the right first, making the elements on the right as large as possible, so as to perform as many merge operations as possible and finally get the maximum element.
Therefore, we can traverse the array from right to left. For each position $i$, where $i \in [0, n - 2]$, if $nums[i] \leq nums[i + 1]$, we update $nums[i]$ to $nums[i] + nums[i + 1]$. Doing so is equivalent to merging $nums[i]$ and $nums[i + 1]$ and deleting $nums[i]$.
In the end, the maximum element in the array is the maximum element in the merged array.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 |
|