The title
Consolidable array: An array is considered consolidable if the difference between two adjacent numbers after sorting is 1.
If [1,5,4,2,3] is sorted by [1,2,3,4,5], the array is a consolidable array
Given an integer array arr, return the maximum integrable subarray length.
If the maximum subarray of [9,20,1,5,4,2,3] is [1,5,4,2,3], return 5
Method of solving violence
Iterate over all subarrays and sort each subarray to see if it fits into a consolidable array.
It’s going to be very complicated, traversing all the subarrays O(n^2), sorting the subarrays O(n log n).
The time is O(n^3 log n) and cannot be sorted in place
Optimization idea
We need to exercise our mental sensitivity when we think about this kind of problem. Can the concept of [consolidable array] be transformed in a way that makes our program more solvable?
After the transformation, we get a set of conditions like this:
-
Non-repeating digit
-
The array length is the maximum value of the array – the minimum value of the array + 1
After conceptual optimization, time complex can be optimized to O(n^2) optimal solution, look at the code
Answer key
package algorithmic.total.solution.common;
import java.util.HashSet;
import java.util.Set;
/ * * *@program: algorithmic-total-solution
* @descriptionConsolidable array: An array is considered consolidable if the difference between two adjacent numbers after sorting is 1. * if [1,5,4,2,3] is sorted by [1,2,3,4,5], the array is consolidable * <p> * given an integer array arr, return the maximum length of the consolidable subarray. * such as,20,1,5,4,2,3 [9] maximum integration subarray for 5 *,5,4,2,3 [1]@author: wangzibin
**/
public class Question2 {
public static void main(String[] args) {
int[] arr = new int[] {9.20.1.5.4.2.3};
System.out.println(getMaxSubIntegrationArray(arr));
}
private static int getMaxSubIntegrationArray(int[] arr) {
if (arr == null || arr.length < 1) {
return 0;
}
int num = 1;
// Evaluates whether the subarray has duplicate elements
Set<Integer> numSet = new HashSet<Integer>();
for (int i = 0; i < arr.length; i++) {
// Clear the start of each change
int max = arr[i];
int min = arr[i];
numSet.clear();
for (int j = i; j < arr.length; j++) {
int currValue = arr[j];
if (numSet.contains(currValue)) {
break;
}
max = Math.max(currValue, max);
min = Math.min(currValue, min);
int distance = max - min;
int length = j - i + 1;
if((j - i) == distance && num < length) { num = length; } numSet.add(currValue); }}returnnum; }}Copy the code