fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. long long maxCrossingSum(const vector<int>& nums, int l, int r, int midVal) {
  7.     // 左半部分（<= midVal）的最大後綴和
  8.     long long leftSum = LLONG_MIN, sum = 0;
  9.     for (int i = l; i <= r; ++i) {
  10.         if (nums[i] > midVal) break; // 超出當前值域範圍
  11.         sum += nums[i];
  12.         leftSum = max(leftSum, sum);
  13.     }
  14.  
  15.     // 右半部分（> midVal）的最大前綴和
  16.     long long rightSum = LLONG_MIN;
  17.     sum = 0;
  18.     for (int i = r; i >= l; --i) {
  19.         if (nums[i] <= midVal) break; // 超出當前值域範圍
  20.         sum += nums[i];
  21.         rightSum = max(rightSum, sum);
  22.     }
  23.  
  24.     // 跨越中值的和
  25.     long long crossSum = (leftSum != LLONG_MIN ? leftSum : 0) + 
  26.                         (rightSum != LLONG_MIN ? rightSum : 0);
  27.  
  28.     return max(leftSum, max(rightSum, crossSum));
  29. }
  30.  
  31. long long valueDivide(const vector<int>& nums, int l, int r, int minVal, int maxVal) {
  32.     if (l == r) return nums[l];
  33.     if (minVal == maxVal) {
  34.         // 所有值相同，直接求和
  35.         long long sum = 0;
  36.         for (int i = l; i <= r; ++i) sum += nums[i];
  37.         return sum;
  38.     }
  39.  
  40.     int midVal = minVal + (maxVal - minVal) / 2;
  41.  
  42.     // 劃分值域
  43.     vector<int> left, right;
  44.     for (int i = l; i <= r; ++i) {
  45.         if (nums[i] <= midVal) left.push_back(nums[i]);
  46.         else right.push_back(nums[i]);
  47.     }
  48.  
  49.     // 遞歸處理左右值域
  50.     long long leftSum = left.empty() ? LLONG_MIN : valueDivide(left, 0, left.size()-1, minVal, midVal);
  51.     long long rightSum = right.empty() ? LLONG_MIN : valueDivide(right, 0, right.size()-1, midVal+1, maxVal);
  52.  
  53.     // 計算跨越中值的和
  54.     long long crossSum = maxCrossingSum(nums, l, r, midVal);
  55.  
  56.     return max(leftSum, max(rightSum, crossSum));
  57. }
  58.  
  59. int main() {
  60.     int n;
  61.     cin >> n;
  62.     vector<int> nums(n);
  63.     int minVal = INT_MAX, maxVal = INT_MIN;
  64.  
  65.     for (int i = 0; i < n; ++i) {
  66.         cin >> nums[i];
  67.         minVal = min(minVal, nums[i]);
  68.         maxVal = max(maxVal, nums[i]);
  69.     }
  70.  
  71.     cout << valueDivide(nums, 0, n-1, minVal, maxVal) << endl;
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin
copy 
5
3 -4 3 -1 2
stdout
copy 
8
https://ideone.com/c6MorE
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!