• API
• FAQ
• Tools
• Archive
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.
Top