Блог пользователя ABhinav2003

Problem 702A — Maximum Increase| What is wrong in this Plz HELP I SPENT 2 Days finding bug PLZZZZ HELP.
Автор ABhinav2003, история, 4 года назад, По-английски 
#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)``
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    sorry bro NOW CHECK IT PLZZZZ

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 года назад, # |
← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить