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

Problem 702A — Maximum Increase | What is wrong in this Plz HELP I SPENT 2 Days finding bug PLZZZZ HELP.
Автор ABhinav2003, история, 5 лет назад, По-английски 
#include<bits/stdc++.h>
using namespace std;
int in=0 , ex;
int sub(int a[] , int len)
{
//	if(len<1)
//		return 0;
	 if(len <= 0  )
		return 0;

	  ex = sub(a,len-1);
	  cout<<"EX "<<ex<<"\n";

	 if(a[len-1] >a[len-2])
	 {
		int t = a[len-1]>a[len-2];cout<<"T "<<t<<"\n";
	 	 in = 1+sub(a,len-1);
	 }
	 cout<<"IN "<<in<<"\n";

	int max1 = max(in,ex);
	cout<<"MAX "<<max1<<"\n";

	return max1;
}

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;
}
[**HERE IS THE PROBLEM**](https://mirror.codeforces.com/problemset/problem/702/A)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

There are many flaws in this code.

  1. Base case is len <= 0 so, when len = 1, the index of a[len-2] will become negative.
  2. in is a global variable, you'll have to add in = 0 before the if statement.

Even if you correct these flaws, the basic flaw is that this method will give you a subsequence instead of a subarray.

For example, for the input 1 2 3 10 4 5 6, your output will be 6 (after correcting the mentioned 2 points).

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

    PLZ CAN U CORRECT MY FLAW AND GIVE IT TO ME I CAN"T UNDERSTAND IT PROPERLY BRO PLZ HELP I AM struggling for about 2-3 days now and not able to do this

    actually i have just started DP PLZ UNDERSTAND AND HELP ME JUST REWRITE THE FUNCTION WITH REMOVING ALL FLAWS

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

      https://www.wikihow.com/Turn-Off-Caps-Lock

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Recursive code which will give TLE
      Memoized version of the same code
      No dp required

      I'd strictly recommend you to learn dp first or you might not understand my solution.

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

    I am having some problem with same question i have applied non dp version same as yours but i am still getting wrong ans in test 5

    heres the code import java.util.Scanner;

    /** * A702 */ public class A702 {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    int highest = 1;

    for (int i = 0; i < a.length; i++) {
        a[i] = sc.nextInt();
    }
    int current = 1;
    for (int i = 1; i < a.length; i++) {
        if (a[i] > a[i - 1]) {
            current++;
        } else if ( current > highest) {
            highest = current;
            current = 1;
        }
    }

    if (current > highest) {
        highest = current;
    }

    System.out.println(highest);

}

    }

    → Ответить
    • »
      »
      »
      10 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      My first ever Java Submission on any website, for you.
      (Well actually 2nd, because 1st was compilation error.)

      Change:

      if (a[i] > a[i - 1]) {
    current++;
} else {
   if ( current > highest) {
        highest = current;
   }
   current = 1; // This has to be done evertime you see non-increasing element.
}
      → Ответить
      • »
        »
        »
        »
        10 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thanks man, yes i noticed that logical error after this post ,but thank you for your response i really appreciate it

        → Ответить