You are not logged in. Please login at www.codechef.com to post your questions!

×

RKABOL05 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

EASY

PREREQUISITES:

DP,Longest Increasing Subsequence.

PROBLEM:

Given an array of N integers, we need to find the length of the longest increasing subsequence such that difference between two consecutive elements in the sequence is exactly equal to 1.

EXPLANATION:

In this question, we can find the length of longest increasing subsequence by maintaining an array dp[maxi]. Let dp[k] indicate the length of the longest increasing subsequence ending with integer k. Thus by iterating through the array, we can calculate the length of increasing subsequence upto the index i ending with a[i] as dp[a[i]]=dp[a[i]-1]+1. And finding the maximum value of the dp array gives us the length of the longest increasing subsequence with the given constraint.

Based on the implementation, If you use an hash table like an array, the time complexity will be O(n). If you use map, the time complexity will be O(n logn). Both solutions will pass.

AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

asked 13 Mar, 15:58

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:37

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,182
×3,673
×19
×19
×19

question asked: 13 Mar, 15:58

question was seen: 143 times

last updated: 15 Mar, 13:37