fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //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, 0);
  8.     int currentMax = nums[0];
  9.     prefixMaxSum[0] = nums[0];
  10.  
  11.     for (int i = 1; i < n; ++i) {
  12.         currentMax = max({0, nums[i], currentMax + nums[i]});
  13.         prefixMaxSum[i] = currentMax;
  14.     }
  15.  
  16.     return prefixMaxSum;
  17. }
  18.  
  19. //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, 0);
  23.     int currentMax = nums[n-1];
  24.     suffixMaxSum[n-1] = nums[n-1];
  25.  
  26.     for (int i = n - 1; i >= 0; 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+1, 0);
  43.     maxPrefixSum[0] = prefixMaxSum[0];
  44.     for (int i = 1; i < n; ++i) {
  45.         maxPrefixSum[i] = max(maxPrefixSum[i - 1], prefixMaxSum[i]);
  46.     }
  47.  
  48.     vector<int> maxSuffixSum(n+1, 0);
  49.     maxSuffixSum[n-1] = suffixMaxSum[n-1];
  50.     for (int i = n - 1; i >= 0; i--) {
  51.         maxSuffixSum[i] = max(maxSuffixSum[i + 1], suffixMaxSum[i]);
  52.     }
  53.  
  54.     int maxSum = 0;
  55.     for (int i = 0; i < n ; ++i) {
  56.     	// cout<<maxSum<<"i is "<<i<<endl;
  57.         maxSum = max(maxSum, maxPrefixSum[i] + maxSuffixSum[i + 1]);
  58.     }
  59.  
  60.     return maxSum;
  61. }
  62.  
  63. int main() {
  64. 	int n;cin>>n;
  65.     vector<int> nums(n);
  66.     for(int i=0;i<n;i++){
  67.     	cin>>nums[i];
  68.     }
  69.     cout << "Maximum sum of two non-overlapping subarrays: " << maxTwoNonOverlappingSubarraysSum(nums) << endl;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5
3 -1 2 1 -2
stdout
copy 
Maximum sum of two non-overlapping subarrays: 6
https://ideone.com/aGuExC
language:
C++ (gcc 8.3)
created:
2 hours 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!