How to optimize the algorithm?

My code solves the problem, but does not fit at the time, it seems to work for n logn as you should. Perhaps something missed in the binary search or in the conditions after leaving it. Now I think that the drawdown is coming at the same elements, i.e. I keep and [5,4] and [5,4,4], although the first is no longer needed and it slows down the search, you can remove it, but it's probably a long time, it is possible to replace None, but have not yet figured out how.
from array import array


def b_search3(xs, q):
 l, h = 0, len(xs)-1
 while l < h:
 mid = (l + h+1)//2
 if q > xs[mid]:
 h = mid -1
else:
 l = mid
 return h


def max_sequence(l):
 temp = list()
 temp.append(array('i', (l[0],)))
 for i, v in enumerate(l[1:]):
 current = b_search3(tuple(x[-1] for x in temp), v)
 if v > temp[current][-1]:
 temp[current][-1] = v
else:
 new = temp[current] + array('i', (v,))
 if len(new) > len(temp):
temp.append(new)
 elif v > temp[len(new)-1][-1]:
 temp[len(new)-1] = new
 answer = []
 prev = 0
 for el in temp[-1]:
 prev += l[prev:].index(el) +1
answer.append(str(prev))
 return '\n'.join((str(len(temp[-1])), ' '.join(answer)))


def main():
 import sys
 reader = (map(int, line.split()) for line in sys.stdin)
next(reader)
 l = array('i')
l.fromlist(list(next(reader)))
print(max_sequence(l))

if __name__ == '__main__':
 main()

Condition:
Given an integer 1≤n≤10^5, and array A[1...n]A[1...n] contains the non-negative integers not exceeding 10^9. Find greatest non-increasing subsequence in A. In the first line output the length k, the second, the indexes 1≤i1
July 12th 19 at 17:12
1 answer
July 12th 19 at 17:14
Solution
Your code can't understand Python I do not know
If for each element A[I] stored L[I] is the length of the max. starting with him and a subsequence P[I] is the index of the next item, then
L[I]=max L[J] : J>I, A[J]<=A[I], the complexity is O(N^2)
I keep the temp in the subsequence for which the index corresponds to the length of this sequence is -1 and the last element of each subsequence no more following popokatepetlem ie - [[6], [6,5], [5,4,3], [5,4,3,3]]. Each new element of l either continues one of the sequences, or start a new one. Speed pass by l for the n time, what to make of the new element is the search for log k temp. Combined rate - n log n as it should be, but I must have a big constant. The signatures on the decision - e-maxx.ru/algo/longest_increasing_subseq_logbut here I can't understand the code. - Noemy_Prosac commented on July 12th 19 at 17:17
Not to understand You, A[0] could be the beginning of rezultirala a subsequence, A[I]>A[0], I>0 and also A[I2]>A[I], I2>I, etc. - increasing subsequence - all candidates in the primary elements - dayna_Grim commented on July 12th 19 at 17:20
: That's right. Explain with an example what the idea is. Need to find the greatest newsrelease sequence, i.e., 4.3 or 4.4 and If we have an array A[1,2,3,3,2] in the first atarasii our potential maximum subsequence A[0], the second A[1], since A[1]>A[0] and can not exist a sequence starting at A[0], which would be longer than the sequence starting at A[1], on the 3rd A[2] for the same reason, on the 4th A[2,3] because A[2]==A[3], and hence any sequence that starts at A[2], is longer than A[3] and on the 5th A[2,3], A[2,3,4] because A[3]>A[4], this means that A[2,3] still has a chance to become the maximum populatevfslist - Noemy_Prosac commented on July 12th 19 at 17:23
A new element can be attached to the tail of ANY subsequence, if it is smaller, but you can not connect
The rapid growth in the number of options
Maybe I still don't understand Your algorithm
Python-ovsky adding to the list (array) is not O(1) - is not this the reason for the drawdown? - dayna_Grim commented on July 12th 19 at 17:26
No, not any, but only in specific, the longest of suitable for [[6], [6,5], [6,4,4]] if you add 3 I'm doing this [[6], [6,5], [6,4,4], [6,4,4,3]]. Adding to a list in Python is O(1), the drawdown has already found were in a - tuple(x[-1] for x in temp should have been learned from the cycle and change on each iteration, but I now memory is not being invested( - Noemy_Prosac commented on July 12th 19 at 17:29
Got it! If the new element X=tail any subsequence L, then L is replaced by (L,X), if X < tail L, then for such L, max length, add the subsequence (L,X). It turns out for any subsequence L in the list are also present and all its prefixes (for a number of first elements including only one head). If X > all tails (i.e., both heads), then add the subsequence of X from one e-TA. Indeed, subsequences always L I in the ith iteration, about the length error. Search and insertion in log(N) needed a MAP sorted by the tail. However, the voraciously memory is used to store all prefixes L, mine tends to O(N^2) - dayna_Grim commented on July 12th 19 at 17:32
All true, tuple(x[-1] for x in temp - this line is this map, which was eating lot of resources, and PAMA Yes O(n^2/2) - Noemy_Prosac commented on July 12th 19 at 17:35
The arrays S[N] is the length of the subsequence starting with A[I] and P[N] is the index of the subsequence element preceding A[I] (it is exactly 1) or -1. The subsequence is specified by its index I of the last element, now the memory is O(N). Subsequence stored in a MAP structure with the streamlining, able to search and add for log(N) sort on last element - dayna_Grim commented on July 12th 19 at 17:38
: You have length 1,2,...,I, length can be the same and decrease, the last element unique - dayna_Grim commented on July 12th 19 at 17:41
So, the length can't be the same and each following one more, the length of the matches array index temp +1, i.e. temp[0] is always a sequence of length 1, and so on. Do it with conditions after search. In short, the algorithm is correct, but eats too much memory and with this I can't handle. And about your last sentence - did not understand a bit, what do you offer me to keep instead of subsequences in order to obtain O(n), could for example show in the map and see no need for my temp array performs the same function. - Noemy_Prosac commented on July 12th 19 at 17:44
A={10,20,...}
1st iteration: {10}
2nd iteration {10} and {20} - dayna_Grim commented on July 12th 19 at 17:47
i.e. to store only the last items in each sequence, perhaps, but I'm not sure I can then restore the latest index and the length of the entire sequence - Noemy_Prosac commented on July 12th 19 at 17:50
If the list is {6,5,4,3,2,1}, that is,{6,5,4,3,2}, {6,5,4,3}, {6,5,4}, {6,5}, {6}
So?
In order not to store all the prefixes that are stored for each item a link to prejudise (if not primary) - prejudise uniquely determined, since the element is added to exactly ONE subsequence.
Then the subsequence is uniquely determined by its last element and easily recovered from it + store the length for quick comparison - dayna_Grim commented on July 12th 19 at 17:53
You keep for each item a link to the previous (clearly defined). Here at the end and unwound the subsequence - dayna_Grim commented on July 12th 19 at 17:56
I don't understand how it is you have an array like temp ordered last elements (binary search time pass) - and he then adds, without losing uporyadochennost - needed insert is O(N) - dayna_Grim commented on July 12th 19 at 17:59
Long you specifically wrong - dayna_Grim commented on July 12th 19 at 18:02
Again an example Danno - [4, 4, 3, 4, 6, 5, 3] for him the greatest non-increasing posledovatelnosti - [4,4,4,3], but if I keep only the last elements, the list of subsequences after exiting the loop will be - [6,5,4,3] and something I do not understand how I to restore the desired consistency - Noemy_Prosac commented on July 12th 19 at 18:05
do not insert and replace, [[6], [6,4], [6,4,4]] next is say 5, the binary search indicates that you need to postaviti on 0 index. I go to 0 index and see where the last element 6, 6 is less than 5 then I copy this array and add to it 5, get [6,5] and replace with the following Elementum, get - [[6], [6,5], [6,4,4]] - Noemy_Prosac commented on July 12th 19 at 18:08
x < tail L - add (L,x), L remains, then it can add another y>x
and even according to you - change element will have to move with a shift other is O(N) one Appendix, N^2 for the entire algorithm

I wrote 2 times: every element is added to only ONE populatevfslist therefore the index of the previous element uniquely determined, it is stored in a separate array P[N], then, knowing the last item - write it down, skip to previous index and so on until you write down all podpole from the end - dayna_Grim commented on July 12th 19 at 18:11
Only store the last element of all prefixes of the same subsequence {6},{6,5}...{6,5,4,3} - keep only 3 (its index) and the index of the previous subsequence in (4), the previous index stored for each of A[I] in the array P[I] - dayna_Grim commented on July 12th 19 at 18:14
C-like pseudocode
https://ideone.com/gW6OcZ - dayna_Grim commented on July 12th 19 at 18:17
: Decided thanks. Used three arrays one keeps the ends of the sequences, the second of their indices, trait all of the previous items. And about the solution with the storage of sequences in the array (array of arrays). The insert is done in linear time, but I never did, I was doing the assignment on the index, and the time constant so that the total - is also O(nlogn), but the memory of n^2 - Noemy_Prosac commented on July 12th 19 at 18:20
I store all the indexes and the index of the previous for EACH element A[N]. Memory O(N)
> General - is also O(nlogn), but the memory of n^2
This can not be if You in each cell of this memory is ever traded, then the time is O( n^2)
Specifically, the copy subsequence is O(N) - dayna_Grim commented on July 12th 19 at 18:23
Take a look https://habrahabr.ru/company/hola/blog/282624
I immediately thought of suffix trees.
But Zip does not compress dictionary 6Mb less than 1.5 Mb and you have to squeeze into 64kB! - dayna_Grim commented on July 12th 19 at 18:26
: The reference is to a cell takes constant time, I'm on the index are traded. But copy Yes, not taken into account, so in General, I think you're right O(n).
I think the problem is not in compression in dictionary or data structures, and to identify patterns in these words and then for these laws to apreciate the word or not. For example if the string contains no consonants, it is not the word. And so a few checks. In the end, the algorithm should give the probability that the word. - Noemy_Prosac commented on July 12th 19 at 18:29
Then difficult, more math
I do rely on compression - dayna_Grim commented on July 12th 19 at 18:32

Find more questions by tags AlgorithmsPython