leetcode3689最大子数组总值I

一、问题描述

二、解题思路

由于本题的子数组可以重复选择，所以，可以使用贪心算法来解决这个问题。遍历数组，找出最大值MAX和最小值MIN，结果即为k*(MAX-MIN)，最后计算返回即可。

三、代码实现

class Solution {
public:
long long maxTotalValue(vector<int>& nums, int k) {
//贪心:找到（最大元素-最小元素）*k
long long ret=0;
int MIN=nums[0],MAX=nums[0];
for(auto x:nums){
MIN=min(x,MIN);
MAX=max(x,MAX);
}
//防止溢出
ret+=(long long)k*(MAX-MIN);
return ret;
}
};