StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POa "divide and conquer" algorithm assignment
text
Body
copied!<p>Now I have N different intergers, I need to find an interval that has the most numbers whose value is between the endpoints of the interval in O(NlogN) time. I call it a "divide and conquer" problem because it is in my final exam's "divide and conquer" category. I have been thinking about it for 2 weeks and have done a lot of experiments, none of them are right(compared to a brute force algorithm). Could someone help me?</p> <p>examples:</p> <p>8,1,3,4,7. The answer is 1-7.</p> <p>2,6,5,4,9,8. The answer is 2-9 or 2-8.</p> <p>I think the word "interval" doesn't express my meaning. I mean to find a subsequence of the array that has the most numbers whose value is between the endpoints of the subsequence. Eg.1: "1,3,4,7" has two numbers(3,4), and eg.2: both "2,6,5,4,9" and "2,6,5,4,9,8" have three numbers(6,5,4). </p> <p>here is my code(O(n^2)). @Vaughn Cato I use this to compare to your code.</p> <pre><code>#! /usr/bin/env python #coding=utf-8 import itertools def n2(numbers): a = [0]*len(numbers) ans = -1 l = 0 r = 0 for j in range(1,len(numbers)): t = 0 for i in range(j-1,-1,-1): if numbers[i]<numbers[j]: x = t - a[i] if x>ans: ans = x l = i r = j t += 1 else: a[i] += 1 return (numbers[l],numbers[r],ans) def countBetween(numbers,left,right): cnt = 0 for i in range(left+1,right): if numbers[left]<numbers[i]<numbers[right]: cnt += 1 return cnt for numbers in itertools.permutations(range(5)): ans1=n2(numbers) ans2=longestInterval(numbers) if(ans1[2]!=ans2[2]): print ans1,ans2,numbers </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload