Why my solution solution to
this problem is incorrect.
Your logic is wrong.
What you need to do, is for every subarray of length > 1 which is non-decreasing, you need to add length*(length-1)/2 to the answer.
For example if you have a subarray 1 2 3 4 -> number of non-decreasing subarrays of length > 1 is lengthC2. Which is length*(length-1)/2. This is because, if you choose any 2 different points out of these 4 points, they will give you a subarray of length > 1 (starting from lower point to higher point).
And finally, add n to the answer. This is for subarrays of length 1.
Make sure to use long long int, as answer can overflow int.
AC code here.
what is wrong in my logic??
What I am trying to do is,
In my solution dp[i] represents no. of subarrays upto ithindex.
What’s your logic behind:
if (a[i-1]<=a[i])dp[i]+=dp[i-1]+1;
Your code gives wrong answer for simple case like:
1
4
1 2 3 4
This should give 10. Your code gives 7.