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

×

Determine the length of the longest increasing contiguous sub-arrays in a given unsorted array.

How to determine the length of the longest increasing contiguous sub-arrays in a given unsorted array?

asked 12 Nov '16, 17:48

rashedcs's gravatar image

1★rashedcs
487419
accept rate: 4%

edited 12 Nov '16, 17:48


since you are finding sub-array which is contiguous, you can apply this.

suppose array is 1 2 1 3 4 3 6

Consider any element, if it is part of increasing subarray, it must be larger than or equal to its previous element.

for 1, no previous element is present, so a subarray ending at 1 will have length 1

for 2, previous element is 1, so 2 is larger. So subarray ending at 2 will have sub-array ending at 1 plus one more element (present 2)

so simple dp approach is

dp[0] = 1 //single element subarray

for(int i = 1; i < n; i++)

if(arr[i] >= arr[i-1])

  dp[i] = dp[i-1] + 1;

else

  dp[i] = 1

maximum among the dp array is the length of the largest contiguous subarray

link

answered 12 Nov '16, 19:03

dragonemperor's gravatar image

3★dragonemperor
8732831
accept rate: 10%

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:

×761

question asked: 12 Nov '16, 17:48

question was seen: 263 times

last updated: 12 Nov '16, 19:03