题解 | 编程题2

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

class Solution {
public:
    long long solve(vector<int>& nums) {
        int n = nums.size();
        
        // 构建桶数组
        vector<vector<int>> buckets(101);
        
        // 构建前缀和数组
        vector<long long> prefix_sum = {0};
        for (int i = 0; i < n; i++) {
            prefix_sum.push_back(prefix_sum.back() + nums[i]);
            buckets[nums[i]].push_back(i);
        }
        
        // 初始化分割点数组和答案
        vector<int> split_points = {-1, n};
        long long ans = 0;
        
        // 遍历每个值的桶
        for (int value = 0; value < 101; value++) {
            auto& positions = buckets[value];
            if (positions.empty()) continue;
            
            sort(positions.begin(), positions.end());
            int itr = 0;
            
            // 计算当前值能得到的最大结果
            for (int pos : positions) {
                while (pos >= split_points[itr]) {
                    itr++;
                }
                ans = max(ans, value * (prefix_sum[split_points[itr]] - 
                                      prefix_sum[split_points[itr-1] + 1]));
            }
            
            // 更新分割点数组
            vector<int> new_points;
            merge(split_points.begin(), split_points.end(),
                  positions.begin(), positions.end(),
                  back_inserter(new_points));
            split_points = new_points;
        }
        
        return ans;
    }
};

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.solve(nums) << endl;
    
    return 0;
}

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

public class Main {
    static class Solution {
        public long solve(int[] nums) {
            int n = nums.length;
            
            // 构建桶数组
            List<List<Integer>> buckets = new ArrayList<>(101);
            for (int i = 0; i < 101; i++) {
                buckets.add(new ArrayList<>());
            }
            
            // 构建前缀和数组
            long[] prefixSum = new long[n + 1];
            for (int i = 0; i < n; i++) {
                prefixSum[i + 1] = prefixSum[i] + nums[i];
                buckets.get(nums[i]).add(i);
            }
            
            // 初始化分割点数组和答案
            List<Integer> splitPoints = new ArrayList<>();
            splitPoints.add(-1);
            splitPoints.add(n);
            long ans = 0;
            
            // 遍历每个值的桶
            for (int value = 0; value < 101; value++) {
                List<Integer> positions = buckets.get(value);
                if (positions.isEmpty()) continue;
                
                Collections.sort(positions);
                int itr = 0;
                
                // 计算当前值能得到的最大结果
                for (int pos : positions) {
                    while (pos >= splitPoints.get(itr)) {
                        itr++;
                    }
                    ans = Math.max(ans, value * (prefixSum[splitPoints.get(itr)] - 
                                               prefixSum[splitPoints.get(itr-1) + 1]));
                }
                
                // 更新分割点数组
                splitPoints.addAll(positions);
                Collections.sort(splitPoints);
            }
            
            return ans;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] nums = new int[n];
        String[] tokens = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(tokens[i]);
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(nums));
    }
}

class Solution:
    def solve(self, nums: list) -> int:
        n = len(nums)
        
        # 构建桶数组
        buckets = [[] for _ in range(101)]
        
        # 构建前缀和数组
        prefix_sum = [0]
        for i, num in enumerate(nums):
            prefix_sum.append(prefix_sum[-1] + num)
            buckets[num].append(i)
        
        # 初始化分割点数组和答案
        split_points = [-1, n]
        ans = 0
        
        # 遍历每个值的桶
        for value, positions in enumerate(buckets):
            if not positions:
                continue
                
            positions.sort()
            itr = 0
            
            # 计算当前值能得到的最大结果
            for pos in positions:
                while pos >= split_points[itr]:
                    itr += 1
                ans = max(ans, value * (prefix_sum[split_points[itr]] - 
                                      prefix_sum[split_points[itr-1] + 1]))
            
            # 更新分割点数组
            split_points = sorted(split_points + positions)
        
        return ans

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