Editorial for Weather Problem.

Правка en1, от srinivas_8025, 2017-02-04 14:10:22

Editorial for Weather Problem.

This problem can be solved easily with dynamic programming.

The answer would always be the count of non-positive numbers in the segment arr[k+1,n] + count of the non-negative numbers in the segment arr[1,k] where 1<=k<n. All we have to do is to keep track of the occurrences of negative and positive integers till ith index.

Let's denote the count of negative numbers by neg[1...n] and pos[1...n] for positive numbers count. So, the count of non-negative numbers in the segment arr[1,i] = i — neg[i]. Similarly, the count of non-positive numbers in the segment arr[i+1,n]= n-i-pos[n]+pos[i]].

Atlast the answer would be min(n-neg[i]-pos[n]+pos[i]) for 1<=i<n.

You can find the code here

Теги dp, #editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский srinivas_8025 2017-02-04 14:10:22 902 Initial revision (published)