S
S
Sheephard2020-08-22 23:08:53
Python
Sheephard, 2020-08-22 23:08:53

How to split a list into sublists?

Given task:

It is necessary to split the list into the minimum number of sublists so that in each of the sublists the first element is the minimum in it, and the last element is the maximum.

The first line of the input contains an integer n (1 ≤n≤ 300000) — the number of elements in the given sequence.

The second line contains n integers a1,a2, ...,an — the given sequence (1 ≤ai≤ 109).
Output

Output a single number — the minimum number of correct segments into which the given sequence can be divided.

Examples:
Input:
6
2 3 1 1 5 1
Output:
3

Input:
4
1 3 2 4
Output:
1

Input:
5
5 4 3 2 1
Conclusion:
5


My code:
flen = int(input())
l = [int(i) for i in input().split()]

vmin = l[0]
imax = 0
k = 1
i = 1
# барьер
l.append(0)

while i <= flen-1:
    if l[i] > l[imax]:
        imax = i
    elif l[i] < vmin or (l[i] == vmin and l[imax] > vmin):  # начало нового подсписка 
        vmin = l[imax+1]
        i = imax + 1
        imax += 1
        k += 1
        continue
    i += 1

print(k)


The testing program gives the wrong answer, although everything is fine on my test data.
What could be wrong?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
H
hint000, 2020-08-23
@Sheephard

Will it be enough if I give a test on which your program fails?
here's a test:
4
1 2 1 3
correct answer: 1
your program's answer: 2
PS okay, the error is in this part:or (l[i] == vmin and l[imax] > vmin)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question