ABhinav2003's blog

By ABhinav2003, history, 4 years ago, In English
#include<bits/stdc++.h>
using namespace std;

int sub(int a[] , int len)
{
	if(len == 0)
		return 0;
	
	if(a[len-1]<a[len-2])
		return 0;

	return max(1+sub(a , len-1) , sub(a , len-2));
}

int main()
{
	int len;
	cin>>len;
	int a[len];
	for(int i = 0;i<=len-1;i++)
	{
		cin>>a[i];
	}
	int m = sub(a , len);
	cout<<m;
}``[LINK TO THE PROBLEM](https://codeforces.com/problemset/problem/702/A)``
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

No link to problem. No insight on approach. Blog asking for help is crap. Great odds of receiving help.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry bro NOW CHECK IT PLZZZZ

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It's quite easy to see why your submission fails. Run it through a debugger (gdb).

      Why does it fail?
      So, how should I solve it?
»
4 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

It's the famous increasing subarray problem which can be solved by dp. I tried to understand what you coded and I think there are fundamental mistakes with logic looking at it.

  • you directly compare last two elements without checking if len > 1

  • in the second if, you should return 1 because individual element is an increasing subarray

  • in the last return you are adding 1,assuming that the subarray takes last two elements into account, but that way you are getting pieces of increasing subarrays and not a single one.

Solution saving maximum value

Note : you can solve it using dp to maintain the length of the longest increasing subarray ending at index i or just maintain the maximum value saving memory. My submission uses the second approach.