fork download 
  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+1];
  8.         for (int i = 1; i <= n; i++) {
  9.             nums[i] = scanner.nextInt();
  10.         }
  11.         System.out.println("Maximum sum of two non-overlapping subarrays: " + maxTwoNonOverlappingSubarraysSum(nums));
  12.     }
  13.  
  14.     public static int maxTwoNonOverlappingSubarraysSum(int[] nums) {
  15.         int n = nums.length - 1;
  16.         if (n == 0) return 0;
  17.  
  18.         int[] prefixMaxSum = calculatePrefixMaxSum(nums);
  19.         int[] suffixMaxSum = calculateSuffixMaxSum(nums);
  20.  
  21.         int[] maxPrefixSum = new int[n + 2];
  22.         maxPrefixSum[1] = prefixMaxSum[1];
  23.         for (int i = 2; i <= n; i++) {
  24.             maxPrefixSum[i] = Math.max(maxPrefixSum[i - 1], prefixMaxSum[i]);
  25.         }
  26.  
  27.         int[] maxSuffixSum = new int[n + 2];
  28.         maxSuffixSum[n] = suffixMaxSum[n];
  29.         for (int i = n - 1; i >= 1; i--) {
  30.             maxSuffixSum[i] = Math.max(maxSuffixSum[i + 1], suffixMaxSum[i]);
  31.         }
  32.  
  33.         int maxSum = 0;
  34.         for (int i = 0; i <= n; i++) {
  35.             maxSum = Math.max(maxSum, maxPrefixSum[i] + maxSuffixSum[i + 1]);
  36.         }
  37.  
  38.         return maxSum;
  39.     }
  40.  
  41.     public static int[] calculatePrefixMaxSum(int[] nums) {
  42.         int n = nums.length - 1;
  43.         int[] prefixMaxSum = new int[n + 1];
  44.         int currentMax = nums[1];
  45.         prefixMaxSum[1] = nums[1];
  46.  
  47.         for (int i = 2; i <= n; i++) {
  48.             currentMax = Math.max(0, Math.max(nums[i], currentMax + nums[i]));
  49.             prefixMaxSum[i] = currentMax;
  50.         }
  51.  
  52.         return prefixMaxSum;
  53.     }
  54.  
  55.     public static int[] calculateSuffixMaxSum(int[] nums) {
  56.         int n = nums.length - 1;
  57.         int[] suffixMaxSum = new int[n + 1];
  58.         int currentMax = nums[n];
  59.         suffixMaxSum[n] = nums[n];
  60.  
  61.         for (int i = n - 1; i >= 1; i--) {
  62.             currentMax = Math.max(0, Math.max(nums[i], currentMax + nums[i]));
  63.             suffixMaxSum[i] = currentMax;
  64.         }
  65.  
  66.         return suffixMaxSum;
  67.     }
  68. }
Success #stdin #stdout 0.17s 56864KB
comments ()
stdin 
5
5 
-3 
-5 
15 
5
stdout 
Maximum sum of two non-overlapping subarrays: 25
https://ideone.com/d6C2EK
language:
Java (HotSpot 12)
created:
16 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!