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

×

Can we find the length of the longest subarray with sum>k efficiently?

Here, 'k' can be any integer.

My O(nlogn) solution is as follows :- https://ideone.com/Ff3CcO

Is there any O(n) algorithm for above?

Thanks.

Note:- 1)I've done my research. 2)No, this problem does not belong to any ongoing contest in the world :-)

asked 23 Jan, 12:55

karangreat234's gravatar image

5★karangreat234
-8639
accept rate: 0%

try variant of Kadane algorithm.

(23 Jan, 19:01) shivam_g14704★

DOES NOT WORK

(23 Jan, 23:12) karangreat2345★

Yes, we can! :)

Precalc prefix and suffix negative sums sorted by sum and length. It can be done at O(n), because we add new sum to already sorted array only if this one is smaller than last.

Use two pointers technics to parse all pretenders and choose the longest.

link

answered 24 Jan, 02:30

batura_dima's gravatar image

5★batura_dima
1264
accept rate: 5%

can u please send the link of the question : )

link

answered 24 Jan, 21:05

himalaya7's gravatar image

5★himalaya7
304
accept rate: 9%

Question is:-https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/ But after we reach the last step of the solution we realize that we have to find the length of the longest sub-array with sum>-2

(24 Jan, 22:55) karangreat2345★
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:

×75
×68
×20

question asked: 23 Jan, 12:55

question was seen: 168 times

last updated: 24 Jan, 22:55