第 468 场周赛Q2——3689. 最大子数组总值 I

题目链接：3689. 最大子数组总值 I（中等）

算法原理：

解法一：排序

24ms击败2.99%

时间复杂度O(Nlogn)

由于同一个子数组可以重复选，所以最优解是，把差值最大的子数组重复选 k 次，所以，我们只需要排序找到最大值和最小值即可

解法二：一次遍历

2ms击败62.69%

时间复杂度O(N)

我们也可以一次遍历，遍历的同时同步更新最大值和最小值

Java代码：

class Solution { //解法一：排序 public long maxTotalValue(int[] nums, int k) { Arrays.sort(nums); long max=nums[nums.length-1]; long min=nums[0]; return (long)(k*(long)(max-min)); } }

class Solution { //解法二：一次遍历 public long maxTotalValue(int[] nums, int k) { int min=0x3f3f3f3f; int max=0; for(int x:nums){ min=Math.min(min,x); max=Math.max(max,x); } return (long)(max-min)*k; } }