解题思路

这是一个区间最值问题。通过观察可以发现，当选择整个数组作为区间时，区间和固定为所有数字之和，而区间最小值就是数组中的最小值。

关键点：

  1. 区间和固定为所有数字之和
  2. 区间最小值必定是数组中的某个数
  3. 要使结果最大，应选择包含最小值的最大区间
  4. 排序后第一个数就是最小值

算法步骤：

  1. 计算数组总和
  2. 找到数组最小值
  3. 计算最小值与总和的乘积

代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long maxIntervalValue(vector<int>& nums) {
        // 计算数组总和
        long long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // 找到最小值
        int minVal = *min_element(nums.begin(), nums.end());
        
        // 返回最小值与总和的乘积
        return sum * minVal;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Solution solution;
    cout << solution.maxIntervalValue(nums) << endl;
    
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static class Solution {
        public long maxIntervalValue(int[] nums) {
            // 计算数组总和
            long sum = 0;
            int minVal = Integer.MAX_VALUE;
            
            for (int num : nums) {
                sum += num;
                minVal = Math.min(minVal, num);
            }
            
            // 返回最小值与总和的乘积
            return sum * minVal;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] nums = Arrays.stream(br.readLine().split(" "))
                          .mapToInt(Integer::parseInt)
                          .toArray();
        
        Solution solution = new Solution();
        System.out.println(solution.maxIntervalValue(nums));
    }
}

class Solution:
    def max_interval_value(self, nums: list) -> int:
        # 计算数组总和和最小值
        total_sum = sum(nums)
        min_val = min(nums)
        
        # 返回最小值与总和的乘积
        return total_sum * min_val

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    
    solution = Solution()
    print(solution.max_interval_value(nums))

算法及复杂度

  • 算法：一次遍历
  • 时间复杂度：，其中 是数组长度
  • 空间复杂度：，只需要常数空间