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 :)
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.
5 . O(N).
It is N log N if elements are <= 10^9, isn't it?
are Unordered_set.Insert() and Unordered_set.Erase() works in O(logN) time?
Obviously s.contains() supposed to be O(1). S can be hashtable or just bool array if constraints on elements are small enough.
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.
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
This works only with non-negative numbers.
i thought another problem in prev edit.
Give Me hint about solving Problem 6.. O(n^2) will be ok ,space O(n^3)
Generating All permutations will give TLE !!!
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?