Hi Codeforces,
Please help me to solve this problem.
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.
Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).
Couldn't you confirm the last test case because there is the splitting 2([1,2],[4])?
Yes you are right it should be 2. If the array is [4,3,2,1] then answer is 1.
Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).
In last testcase, shouldn't be answer 4!!? by splitting array like this [1],[2],[3],[4]
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.
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