fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Function to calculate the maximum subarray sum ending at each index from the left
  5. vector<int> calculatePrefixMaxSum(const vector<int>& nums) {
  6.     int n = nums.size();
  7.     vector<int> prefixMaxSum(n+1, 0);
  8.     int currentMax = nums[1];
  9.     prefixMaxSum[1] = nums[1];
  10.  
  11.     for (int i = 2; i <= n; ++i) {
  12.         currentMax = max({0, nums[i], currentMax + nums[i]});
  13.         prefixMaxSum[i] = currentMax;
  14.     }
  15.  
  16.     return prefixMaxSum;
  17. }
  18.  
  19. // Function to calculate the maximum subarray sum starting at each index from the right
  20. vector<int> calculateSuffixMaxSum(const vector<int>& nums) {
  21.     int n = nums.size();
  22.     vector<int> suffixMaxSum(n+1, 0);
  23.     int currentMax = nums[n];
  24.     suffixMaxSum[n] = nums[n];
  25.  
  26.     for (int i = n - 1; i >= 1; --i) {
  27.         currentMax = max({0, nums[i], currentMax + nums[i]});
  28.         suffixMaxSum[i] = currentMax;
  29.     }
  30.  
  31.     return suffixMaxSum;
  32. }
  33.  
  34. int maxTwoNonOverlappingSubarraysSum(const vector<int>& nums) {
  35.     int n = nums.size();
  36.     if (n == 0) return 0;
  37.  
  38.     // Calculate prefix and suffix max subarray sums
  39.     vector<int> prefixMaxSum = calculatePrefixMaxSum(nums);
  40.     vector<int> suffixMaxSum = calculateSuffixMaxSum(nums);
  41.  
  42.     vector<int> maxPrefixSum(n+2, 0);
  43.     maxPrefixSum[1] = prefixMaxSum[1];
  44.     for (int i = 2; i <= n; ++i) {
  45.         maxPrefixSum[i] = max(maxPrefixSum[i - 1], prefixMaxSum[i]);
  46.     }
  47.  
  48.     vector<int> maxSuffixSum(n+2, 0);
  49.     maxSuffixSum[n] = suffixMaxSum[n];
  50.     for (int i = n - 1; i > 0; --i) {
  51.         maxSuffixSum[i] = max(maxSuffixSum[i + 1], suffixMaxSum[i]);
  52.     }
  53.  
  54.     // Find the maximum sum of two non-overlapping subarrays
  55.     int maxSum = 0;
  56.     for (int i = 0; i <= n ; ++i) {
  57.     	// cout<<maxSum<<"i is "<<i<<endl;
  58.         maxSum = max(maxSum, maxPrefixSum[i] + maxSuffixSum[i + 1]);
  59.     }
  60.  
  61.     return maxSum;
  62. }
  63.  
  64. int main() {
  65. 	int n;cin>>n;
  66.     vector<int> nums(n+1);
  67.     for(int i=1;i<=n;i++){
  68.     	cin>>nums[i];
  69.     }
  70.     cout << "Maximum sum of two non-overlapping subarrays: " << maxTwoNonOverlappingSubarraysSum(nums) << endl;
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum sum of two non-overlapping subarrays: 0
https://ideone.com/LCdhgE
language:
C++14 (gcc 8.3)
created:
8 days 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!