- array-rearrange, Arrays, Dynamic Programming, Kadane, subarray, subarray-sum

Maximum subarray sum possible after removing at most one subarray

import java.io.*;import java.util.*;  class GFG {                  public static void maximumSum(        int arr[], int n)    {        long[] preSum = new long[n];          long sum = 0;        long maxSum = 0;                  for (int i = 0; i < n; i++) {                          sum = Math.max(arr[i],                           sum + arr[i]);                          maxSum = Math.max(maxSum,                              sum);                          preSum[i] = maxSum;        }          sum = 0;        maxSum = 0;          long[] postSum = new long[n + 1];                  for (int i = n - 1; i >= 0; i–) {                          sum = Math.max(arr[i],                           sum + arr[i]);                          maxSum = Math.max(maxSum,                              sum);                          postSum[i] = maxSum;        }                          long ans = 0;          for (int i = 0; i < n; i++) {                          ans = Math.max(ans,                           preSum[i]                               + postSum[i + 1]);        }                  System.out.println(ans);    }          public static void main(String[] args)    {        int arr[] = { 7, 6, -1, -4, -5, 7, 1 };        maximumSum(arr, arr.length);    }}