How do I do this question?
asked 19 Jul '15, 10:15

For any position i in the array, for what length "window" can that number act as strength ? Clearly, the 2 at 3rd position (0th based indexing) will act as strength for the windows of length 1,2 and 3 only. This is because,if you expand the window on either side, we have the number 1 ( <2 ) and number 0 ( <2) . So, for each index i we need to find the largest index j < i such that a[j] < a[i]. Let's store it in l[i]. You can calculate arrays l and r using a stack and then solve the problem. answered 27 Jul '16, 11:47

There is one very simple method. You can easily find the answer for x = 1. Initialize the array, a[200005][200005]. Therefore, a[1][1] = a1, a[1][2] = a2, ..., a[1][i] = ai, ..., a[1][n] = an. In the loop you can store maximum strength in tempmax while assigning values to the array. print  tempmax tempmax = 0 Now for x = 2. a[2][2] = min(a[1][1], a[1][2]), a[2][3] = min(a[1][2], a[1][3]), ..., a[2][i] = min(a[1][i1], a[1][i]), ..., a[2][n] = min(a[1][n1], a[1][n]). print  tempmax ... tempmax = 0 For x = i. a[x][x] = min(a[x1][x1], a[x1][x]), a[x][x+1] = min(a[x1][x], a[x1][x+1]), ..., a[x][x+i] = min(a[x1][x+i1], a[x1][x+i]), ..., a[x][n] = min(a[x1][n1], a[x1][n]). print  tempmax ... tempmax = 0 For x = n a[n][n] = min(a[n1][n1], a[n1][n]) if(a[n][n] > tempmax) tempmax = a[n][n]. printf  tempmax Now comes the question that logic is perfectly fine, but we can't declare such a huge array. Again, there is a simple solution for that. The method to implement it using 1D array is as follows: declare array a[200005] tempmax = 0; x = 1: for(i=n to 1){ a[i] = ai; if(a[i]>tempmax) tempmax = a[i]; } printf("%d ", tempmax); tempmax = 0; x = 2: for(i=n to 2){ a[i] = min(a[i], a[i1]); if(a[i]>tempmax) tempmax = a[i]; } printf("%d ", tempmax); ... tempmax = 0; x = j: for(i=n to j){ a[i] = min(a[i], a[i1]); if(a[i]>tempmax) tempmax = a[i]; } printf("%d ", tempmax); ... tempmax = 0; x = n: for(i=n to n){ a[i] = min(a[i], a[i1]); if(a[i]>tempmax) tempmax = a[i]; } printf("%d ", tempmax); Now I guess you got the notion about how to approach the question. The final code which you can implement is as follows: //min function int n, a[200005], tempmax, i, j; //read the inputs tempmax = 0; for(i=1;i<=n;i++){
} printf("%d ", tempmax); for(j=2;j<=n;j++){
} But this method isn't sufficient as it will give TLE. Please implement it using BIT. answered 27 Jul '16, 15:10
