建设网站的要点,做网站的公司怎么发展业务,企业手机网站建设讯息,数字创意设计包括哪些工具题目链接 Leetcode.2789 合并后数组中的最大元素 rating : 1485 题目描述
给你一个下标从 0 0 0 开始、由正整数组成的数组 n u m s nums nums 。
你可以在数组上执行下述操作 任意 次#xff1a;
选中一个同时满足 0 ≤ i n u m s . l e n g t h − 1 0 \leq i
选中一个同时满足 0 ≤ i n u m s . l e n g t h − 1 0 \leq i nums.length - 1 0≤inums.length−1 和 n u m s [ i ] ≤ n u m s [ i 1 ] nums[i] \leq nums[i 1] nums[i]≤nums[i1] 的整数 i i i。将元素 n u m s [ i 1 ] nums[i 1] nums[i1] 替换为 n u m s [ i ] n u m s [ i 1 ] nums[i] nums[i 1] nums[i]nums[i1] 并从数组中删除元素 n u m s [ i ] nums[i] nums[i] 。
返回你可以从最终数组中获得的 最大 元素的值。
示例 1 输入nums [2,3,7,9,3] 输出21 解释我们可以在数组上执行下述操作 选中 i 0 得到数组 nums [5,7,9,3] 。选中 i 1 得到数组 nums [5,16,3] 。选中 i 0 得到数组 nums [21,3] 。 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。 示例 2 输入nums [5,3,3] 输出11 解释我们可以在数组上执行下述操作 选中 i 1 得到数组 nums [5,6] 。选中 i 0 得到数组 nums [11] 。 最终数组中只有一个元素即 11 。 提示 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105 1 ≤ n u m s [ i ] ≤ 1 0 6 1 \leq nums[i] \leq 10^6 1≤nums[i]≤106
解法贪心
我们用 s s s 表示每一段能够合并的元素之和 s s s 初始为 n u m s [ n − 1 ] nums[n-1] nums[n−1]。
我们用 a n s ans ans 表示最大的元素值 a n s ans ans 初始为 n u m s [ n − 1 ] nums[n-1] nums[n−1]。
我们从逆序开始遍历 n u m s [ i ] ( 0 ≤ i ≤ n − 2 ) nums[i] \quad (0 \leq i \leq n - 2) nums[i](0≤i≤n−2)
如果 s ≥ n u m s [ i ] s \geq nums[i] s≥nums[i]说明 s s s 可以和 n u m s [ i ] nums[i] nums[i] 合并 s s s 合并之后的值为 s n u m s [ i ] s nums[i] snums[i]否则说明 s s s 不可以和 n u m s [ i ] nums[i] nums[i] 合并那么 s s s 就要以 n u m s [ i ] nums[i] nums[i] 开始合并也就是 s n u m s [ i ] s nums[i] snums[i]
在遍历的过程中 a n s ans ans 取最大的 s u m sum sum也就是最大的元素。
时间复杂度 O ( n ) O(n) O(n)
C代码
using LL long long;class Solution {
public:long long maxArrayValue(vectorint nums) {int n nums.size();LL ans nums[n - 1] , s nums[n - 1];for(int i n - 2;i 0;i--){if(s nums[i]) s nums[i];else s nums[i];ans max(ans , s);}return ans;}
};
