Write a method that uses a divide-and-conquer strategy to find the maximum value

Question

Write a method that uses a divide-and-conquer strategy to find the maximum value in an integer array. The maximum value of a one-element array is that element. The maximum of any other array is the maximum of the left half, or the maximum of the right half, whichever is larger.

How many balls are in this pyramid?

Each level in the pyramid is a square, so if there are n levels, the bottom level has n * n balls, and the total number of balls is just

(n * n) + (number of balls in a pyramid of height n - 1).

There is just one ball in a pyramid of height 1. Write a static recursive method getPyramidCount that takes a single int argument representing the number of levels in a pyramid, and returns the total number of balls.

Explanation / Answer

Please find my implementation for Q1.

Please repost others in separate post.

The following code find the max from an array.

public class ArrayMax
{
public static void main(String[] args)
{
int[] test = {3, 7, 9, 1, 2, 3, 2,7,10}; // sum should be 20
int result = arrayMax(test);
System.out.println(result);
}

public static int arrayMax(int[] arr)
{
return arrayMaxRec(arr, 0, arr.length - 1);
}

private static int arrayMaxRec(int[] arr, int start, int end)
{
if (start == end)
{
return arr[start];
}
else
{
int mid = (start + end) / 2;
int leftSum = arrayMaxRec(arr, start, mid);
int rightSum = arrayMaxRec(arr, mid + 1, end);
return (leftSum>rightSum)?leftSum:rightSum;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.