It is preferrable to read the pdf statment.
Cuber QQ, who is the producer of Breaking News, is tired of all the pressures from producing high-quality content and making sponsors happy. The most painful part of this job is, actually, to put all the news clips into units, between which advertisements are broadcast. Recently, after acquiring some knowledge from technology department, he found that he can actually leverage some help from algorithms.
Formally, the sequence of news clips to be broadcast tonight is a sequence a consisting of n integers, where a=a1,a2,…,an (ai∈{−1,0,1}), which are the expected quality of those news clips. Being of negative quality does not mean that the clip will not be broadcast. Actually all the contents have already been carefully selected to fit the length of the TV show. Also, the clips should follow the order, which is already carefully arranged.
To insert ads between clips, Cuber QQ asks you to split the sequence into m (m≥1) non-empty units, i.e., consecutive subsequences, so that every clip belongs to exactly one unit. Formally, if the k-th unit is alk,alk+1,⋯,ark, then rk+1=lk+1 for all 1≤k<m.
Furthermore, each unit should be of moderate length, neither too long nor too short. Formally, L≤ri−li+1≤R should hold for all 1≤k≤m.
The quality of a unit, is defined to be 1 if quality sum of its corresponding clips is greater than 0, -1 if the sum is lower than 0, and 0 otherwise. This can be formulated with vk=[(∑rki=lkai)>0]−[(∑rki=lkai)<0].
The problem is to determine the optimal m and the split plan, to maximize the sum of values of all units, i.e., to maximize ∑mk=1vk.