fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scanner = new Scanner(System.in);
  6.         int n = scanner.nextInt();
  7.         int[] nums = new int[n];
  8.         for (int i = 0; i < n; i++) {
  9.             nums[i] = scanner.nextInt();
  10.         }
  11.         System.out.println("Maximum sum of two non-overlapping subarrays: " + maxTwoSubarraySum(nums));
  12.     }
  13.  
  14.     public static int maxTwoSubarraySum(int[] nums) {
  15.         int n = nums.length;
  16.         if (n == 0) return 0;
  17.  
  18.         int[] leftMax = new int[n];
  19.         int[] rightMax = new int[n];
  20.  
  21.         int currentSum = 0, bestSum = Integer.MIN_VALUE;
  22.         for (int i = 0; i < n; i++) {
  23.             currentSum = Math.max(nums[i], currentSum + nums[i]);
  24.             bestSum = Math.max(bestSum, currentSum);
  25.             leftMax[i] = bestSum;
  26.         }
  27.  
  28.         currentSum = 0;
  29.         bestSum = Integer.MIN_VALUE;
  30.         for (int i = n - 1; i >= 0; i--) {
  31.             currentSum = Math.max(nums[i], currentSum + nums[i]);
  32.             bestSum = Math.max(bestSum, currentSum);
  33.             rightMax[i] = bestSum;
  34.         }
  35.  
  36.         int maxSum = Integer.MIN_VALUE;
  37.         for (int i = 0; i < n - 1; i++) {
  38.             maxSum = Math.max(maxSum, leftMax[i] + rightMax[i + 1]);
  39.         }
  40.  
  41.         return maxSum;
  42.     }
  43. }
  44.  
Success #stdin #stdout 0.21s 59040KB
comments ()
stdin
copy 
7
1
5
-3
4
-9
9
2
stdout
copy 
Maximum sum of two non-overlapping subarrays: 18
https://ideone.com/g9ZX0s
language:
Java (HotSpot 12)
created:
22 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!