fork download
copy 
  1. import java.util.*;
  2. import java.lang.Math;
  3.  
  4. public class Main {
  5.  
  6. 	//Declare global variables low and high
  7. 	static int low;
  8. 	static int high;
  9.  
  10. 	//Find max sum in array arr
  11. 	static int maxCrossSum(int arr[], int start, int mid, int end) {
  12. 		int sum = 0;
  13. 		int leftSum = Integer.MIN_VALUE;
  14. 		for (int i = mid; i >= start; i--) {
  15. 			sum = sum + arr[i];
  16. 			if (sum > leftSum) {
  17. 				low = i;
  18. 				leftSum = sum;
  19. 			}
  20. 		}
  21.  
  22. 		sum = 0;
  23. 		int rightSum = Integer.MIN_VALUE;
  24. 		for (int i = mid; i <= end; i++) {
  25. 			sum = sum + arr[i];
  26. 			if (sum > rightSum) {
  27. 				high = i;
  28. 				rightSum = sum;
  29. 			}
  30. 		}
  31.  
  32. 		return Math.max(leftSum + rightSum - arr[mid], Math.max(leftSum, rightSum));
  33. 	}
  34.  
  35. 	//divide-and-conquer
  36. 	static int divideAndConquer(int arr[], int start, int end) {
  37. 		if (start > end)
  38. 			return Integer.MIN_VALUE;
  39. 		if (start == end)
  40. 			return arr[start];
  41.  
  42. 		//divide
  43. 		int mid = (start + end) / 2;
  44.  
  45. 		//conquer
  46. 		return Math.max(Math.max(divideAndConquer(arr, start, mid - 1), divideAndConquer(arr, mid + 1, end)), maxCrossSum(arr, start, mid, end));
  47. 	}
  48.  
  49. 	public static void main(String[] args) {
  50.  
  51. 		Scanner sc = new Scanner(System.in);
  52. 		int index = sc.nextInt();
  53.  
  54. 		//array size declaration
  55. 		int[] arr = new int[index];
  56. 		//Enter an array value
  57. 		for (int i = 0; i < arr.length; i++) {
  58. 			arr[i] = sc.nextInt();
  59. 		}
  60.  
  61. 		//Calculation
  62. 		int maxSum = divideAndConquer(arr, 0, index - 1);
  63.  
  64. 		//Print
  65. 		System.out.println(low );
  66. 		System.out.println(high);
  67. 		System.out.println(maxSum);
  68. 	}
  69. }
Success #stdin #stdout 0.13s 49296KB
comments (?)
stdin
copy 
11
3
-66
-10
-54
-24
-4
18
36
2
3
-42
stdout
copy 
5
9
59
https://ideone.com/zNDb2p
language:
Java (HotSpot 12)
created:
1 year 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!