fork download 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int[] arr = new int[n + 1]; 
  8.         for (int i = 1; i <= n; i++) {
  9.             arr[i] = sc.nextInt();
  10.         }
  11.         int ans = maxTwoSubarrays(arr);
  12.         System.out.println("Maximum sum of two non-overlapping subarrays: " + ans);
  13.     }
  14.  
  15.     public static int maxTwoSubarrays(int[] arr) {
  16.         int n = arr.length - 1;
  17.         if (n == 0) return 0;
  18.  
  19.         int[] leftBest = buildPrefix(arr);
  20.         int[] rightBest = buildSuffix(arr);
  21.  
  22.         int[] maxLeft = new int[n + 2];
  23.         maxLeft[1] = leftBest[1];
  24.         for (int i = 2; i <= n; i++) {
  25.             maxLeft[i] = Math.max(maxLeft[i - 1], leftBest[i]);
  26.         }
  27.  
  28.         int[] maxRight = new int[n + 2];
  29.         maxRight[n] = rightBest[n];
  30.         for (int i = n - 1; i >= 1; i--) {
  31.             maxRight[i] = Math.max(maxRight[i + 1], rightBest[i]);
  32.         }
  33.  
  34.         int best = 0;
  35.         for (int i = 1; i < n; i++) {
  36.             best = Math.max(best, maxLeft[i] + maxRight[i + 1]);
  37.         }
  38.  
  39.         return best;
  40.     }
  41.  
  42.     private static int[] buildPrefix(int[] arr) {
  43.         int n = arr.length - 1;
  44.         int[] pref = new int[n + 1];
  45.         int run = arr[1];
  46.         pref[1] = run;
  47.         for (int i = 2; i <= n; i++) {
  48.             run = Math.max(arr[i], run + arr[i]);
  49.             run = Math.max(run, 0);
  50.             pref[i] = run;
  51.         }
  52.         return pref;
  53.     }
  54.  
  55.     private static int[] buildSuffix(int[] arr) {
  56.         int n = arr.length - 1;
  57.         int[] suff = new int[n + 1];
  58.         int run = arr[n];
  59.         suff[n] = run;
  60.         for (int i = n - 1; i >= 1; i--) {
  61.             run = Math.max(arr[i], run + arr[i]);
  62.             run = Math.max(run, 0);
  63.             suff[i] = run;
  64.         }
  65.         return suff;
  66.     }
  67. }
  68.  
Success #stdin #stdout 0.16s 57056KB
comments (?)
stdin 
7
1 5 -3 4 -9 9 2
stdout 
Maximum sum of two non-overlapping subarrays: 18
https://ideone.com/Ei2gwP
language:
Java (HotSpot 12)
created:
3 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!