SHARE
TWEET

Untitled

a guest Feb 18th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // A Divide and Conquer based Java
  2. // program for maximum subarray sum
  3. // problem
  4. import java.util.*;
  5.  
  6. class GFG {
  7.  
  8.     // Find the maximum possible sum in arr[]
  9.     // such that arr[m] is part of it
  10.     static int maxCrossingSum(int arr[], int l,
  11.                                 int m, int h)
  12.     {
  13.         // Include elements on left of mid.
  14.         int sum = 0;
  15.         int left_sum = Integer.MAX_VALUE;
  16.         for (int i = m; i >= l; i--)
  17.         {
  18.             sum = sum + arr[i];
  19.             if (sum < left_sum)
  20.             left_sum = sum;
  21.         }
  22.  
  23.         // Include elements on right of mid
  24.         sum = 0;
  25.         int right_sum = Integer.MAX_VALUE;
  26.         for (int i = m + 1; i <= h; i++)
  27.         {
  28.             sum = sum + arr[i];
  29.             if (sum < right_sum)
  30.             right_sum = sum;
  31.         }
  32.  
  33.         // Return sum of elements on left
  34.         // and right of mid
  35.         return left_sum + right_sum;
  36.     }
  37.  
  38.     // Returns sum of maxium sum subarray
  39.     // in aa[l..h]
  40.     static int maxSubArraySum(int arr[], int l,
  41.                                     int h)
  42.     {
  43.     // Base Case: Only one element
  44.     if (l == h)
  45.         return arr[l];
  46.  
  47.     // Find middle point
  48.     int m = (l + h)/2;
  49.  
  50.     /* Return maximum of following three
  51.     possible cases:
  52.     a) Maximum subarray sum in left half
  53.     b) Maximum subarray sum in right half
  54.     c) Maximum subarray sum such that the
  55.     subarray crosses the midpoint */
  56.     return Math.min(Math.min(maxSubArraySum(arr, l, m),
  57.                     maxSubArraySum(arr, m+1, h)),
  58.                     maxCrossingSum(arr, l, m, h));
  59.     }
  60.  
  61.     /* Driver program to test maxSubArraySum */
  62.     public static void main(String[] args)
  63.     {
  64.     int arr[] = {10, -5, 3, -18, 7};
  65.     int n = arr.length;
  66.     int max_sum = maxSubArraySum(arr, 0, n-1);
  67.    
  68.     System.out.println("Maximum contiguous sum is "+
  69.                                         max_sum);
  70.     }
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top