### Nanthakumar06's blog

By Nanthakumar06, 3 months ago,

Hi Codeforces,

You are given an array of size N.

A special subarray of Arr is choosen keeping the following conditions in mind

Let the length of first array choosen must be len-1 the length of last subarray choosen must be 1

Let sum of ith subarray is X and (i+1)th is Y then X must be less than Y

The choosen array must not overlap

Find the maximum length of special subarray(if max length is N, then the subarrays of length N,N-1....,1 must exists and sum of those subarrays must increasing) that could be choosen from Arr

Note It is given that you are only allowed to choose subarray in order of their occurrence in Arr This Means that index of all elements in first choosen subarray will always be less than the index of all elements choosen in second subarray and so on

Constraints 1 <= N <= 100000 1 <= Arr[i] <= 1000000000

Test cases: 1. A = [2,1,3,5,8,6,15] Here, the answer is 3([2,1,3],[5,8],[15]) We can split the array of length 3,2,1 and the sum also increasing. 2. A = [1,2,3,4] For the above array the answer is 2 because [1,2],[4] we cannot split the array for more than length 2.

• 0

 » 3 months ago, # |   0 Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).
 » 3 months ago, # |   0 Couldn't you confirm the last test case because there is the splitting 2([1,2],[4])?
•  » » 3 months ago, # ^ |   0 Yes you are right it should be 2. If the array is [4,3,2,1] then answer is 1.
 » 3 months ago, # |   0 Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 In last testcase, shouldn't be answer 4!!? by splitting array like this [1],[2],[3],[4]
•  » » 3 months ago, # ^ |   0 It should be 1. Because what we need to return is the maximum length. If I am going to split the array as 4, then I need 3 length subarray, 2 length subarray, and a one length subarray and also the sum of the subarray must increase as length decrease. So for [1,2,3,4] we can split as [1,2] and [4] as the sum of 3 and 4 respectively and the result is 2(the max length). We can ignore the [3] subarray in this case.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Ohh, it's written maximum number of special subarrays, so I thought it's talking about number of such subarrays...in that it's right 2 must be ans