Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Matrix.code's blog

Maximum Length of sub-Array
By Matrix.code, 9 years ago, In English 
I have found many problems Involving
To **find the length of the sub-array with varied property**
An array of whole (Positive,0,Negative ) ::

1. Find the length sub-array which have maximum Sum ( First maximise sum , then length )
Solution : kadane Algorithm O(n) for 1D , O(n^3) for 2D

2. Find the largest sub-array which elements_sum <= N ( First maximise length , then minimise sum as possible )
Solution : ?? If O(n) possible ?? I found one with O(n log n)

3. Find the largest sub-array which elements_sum is divisible by a number Q
Solution : O(n) Solution exists . [here](http://stackoverflow.com/questions/16605991/number-of-subarrays-divisible-by-k?rq=1)

4. Find the largest sub-sequences which elements form an arithmetic progression / geometric progration 
Solution : O(n^2) [Here](http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/) Can We do better ??? 

5. Find the largest sub-array where all the elements are different
Solution : I know O(n^2) , O(n) possible ?? or better solution . Please

6. Find A permutation of an array  which sum_of_score is maximum (Here score =
 |(previous_position_of_an_element - current_position_of_an_element)| * element_value )

Solution : ???


...... And More & More

Please discuss about this problem and Find if we can make better :)
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

5) I think we can do BinarySearch. Now we want check: is there at least 1 good segment with length == mid. Just iterate left position of our segment. and now we should answer: is segment [lf, lf + mid — 1] good? It can be done using segment tree, where in vertex of segmnet tree we store Unordered_set.

My eng is bad.

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

5 . O(N).

R = 0;
for (int L = 0; L < N; ++L)
{
   while (R < N && !s.contains(a[R]))
   {
      s.add(a[R]);
      R++;
   }
   // check [L, R) for maximum
   s.erase(a[L]);
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is N log N if elements are <= 10^9, isn't it?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      are Unordered_set.Insert() and Unordered_set.Erase() works in O(logN) time?

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Isnt it N log N
s.contains(a[R])) take log N time per checking 
If while loop is called at least N times . So s.contains(a[R])) called N times
This makes the algorithm running Nlog N

Am I right ? Alias
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Obviously s.contains() supposed to be O(1). S can be hashtable or just bool array if constraints on elements are small enough.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can do problem 5 in O(n) with this algorithm: -start with L and R at 1 -Try to extend [L,R] as much as possible while a[R+1] isn't in [L,R].(this can be done with map,or better with hash,it depends on how big numbers are) -When a[R+1] is in [L,R](we want to take a[R+1] in our sub-array),L will become M[a[R+1]]+1(M[x]-the right most position of x till now)

Greedy solution.

It can be done in O(N*logN) with binary search starting from this fact.If the longest sub-array has length x,then be sure that for every i=(1,x-1),we can find a valid sub-array.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The greedy solution works also for the 2nd problem with O(n).Be aware that hash is needed to store those rightmost positions,because it has O(1) time for insertion,deletion,search

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Give Me hint about solving Problem 6.. O(n^2) will be ok ,space O(n^3)

Generating All permutations will give TLE !!!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Every swap increases/decreases a certain amount of value to the result if for each element we know its initial position. So in O(n^2) we can look for every swap that increases the result and apply it (in a manner similar to selection sort).

    P.S. Can you provide a link to the problem?

    → Reply