CODEWITHSUNDEEP
javaarrays
J.Doe
J.Doe

Reputation: 15

Subarray counting-help needed

I was going through a problem on CodeChef (https://www.codechef.com/problems/SUBINC) on counting subarrays which are strictly non-decreasing. Despite reading through the description several times, I was unable to decipher what I was expected to do.

I was mainly having a problem with two statements:

1)*"All valid subarrays are A[1, 1], A[1, 2], A[2, 2], A[3, 3], A[3, 4], A[4, 4]."*

If the subarray was 1 4 2 3, then how are A[2,2];A[3,3];A[3,4];and A[4,4] valid?(Given that it is non-decreasing only if forward elements are in decreasing order)Also why is A[1,1] valid?

2)"Only single subarray A[1, 1] is non-decreasing."

Similar problem here. If the array itself is only 1 then how can you count A[1,1] is a sub-array?

Perhaps I have completely failed to perceive what is to be done as this problem has been solved by many, but a bit of help would really be appreciated.

P.S I code in Java and am not so comfortable in C so that is why I could not understand most of the submissions.

Upvotes: 1

Views: 455

Answers (1)

Dmitry P.
Dmitry P.

Reputation: 834

Ok, you have an array of four numbers 1 4 2 3

The notation A[i, j] says: "Take all elements of the array from the index i to the index j".

A[1,2] will represent a subarray: 1 4

A[1,3] will represent a subarray: 1 4 2

A[1,4] will be the whole array: 1 4 2 3

And any single element of the array is a subarray too, so when we say A[1,1] it means we need to take the elements starting from the index 1 to the index 1, so it will be just one number: 1

(A[2,2] is 4 therefore and so on).

Non-decreasing means that the next element of array must not be less that the previous. So a one-element array is always non-decreasing, the next element in it just doen't exist (so it's can't be less).

Upvotes: 3

Related Questions