Question

we are given an array a consisting of n distinct integers. we would like to sort array A into ascending order using a simple algorithm. First we divide it into one or more slieces ( a slice is a contiguous sub array. Then we sort each slice. After that, we join the sorted slices in the same order. Write a function solution that returns the max number of slices for which the algorithm will return a correctly sorted array

Answer 1

Answer:

Check the explanation

Explanation:

the js code is as follows

function count_max_group(ar) {

if (ar.length < 2) return ar.length; // if no of elements are 2 then max groups are 2

let st = [0]; // stack to store the groups

for (let i = 1; i < ar.length; i++) {

if (ar[i] >= ar[i - 1]) st.push(i); // pushing elements if if ar[i] is greater than the previous element

for (let j = i; j > 0 && ar[j] < ar[j - 1]; j--) { // finding the max number of grps

swap(ar, j, j - 1); // swapping

if (j <= st[st.length - 1]) st.pop();

}

}

return st.length;

}

function swap(a, i, j) { // function to swap two variables

let t = a[i];

a[i] = a[j];

a[j] = t;

}

//sample solutions

console.log("the sample solutions are\n");

console.log("[2,1,6,4,3,7]\n");

console.log(count_max_group([2,1,6,4,3,7]));

console.log("[4,3,2,6,1]\n") ;

console.log(count_max_group([4,3,2,6,1]));

console.log("[2,4,1,6,5,9,7]\n");

console.log(count_max_group([2,4,1,6,5,9,7]));