Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package magicbox;
- import java.util.Scanner;
- public class DivideEtImpera {
- private static final Scanner cin = new Scanner(System.in);
- private static int n;
- private static int[] a;
- // a = 1, 2, 4, 7, 5, 9, 4
- // 1 2 3 4 5 6 7
- private static int getMaxTeo(int left, int right) {
- int maxVal = 0;
- for (int i = left; i <= right; ++i)
- if (maxVal <= a[i]) maxVal = a[i];
- return maxVal;
- }
- private static int getMaxDAC(int left, int right) {
- if (left == right)
- return a[left];
- if (left + 1 == right)
- return Math.max(a[left], a[right]);
- int middle = (left + right) / 2;
- return Math.max(getMaxDAC(left, middle), getMaxDAC(middle + 1, right));
- }
- public static void main() {
- n = cin.nextInt();
- a = new int[n + 1];
- for (int i = 1; i <= n; ++i)
- a[i] = cin.nextInt();
- System.out.println("The max value calculated with the normal method: " + getMaxTeo(1, n));
- System.out.println("The max value calculated with divide and conquer is: " + getMaxDAC(1, n));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement