can find one more solution in my blog
http://pandey123.wordpress.com/
check it... and tell me if you have any doubt...
On Sat, Jun 23, 2012 at 11:52 PM, Akshat Sapra sapraaks...@gmail.comwrote:
To do this question in O(n) time follow the post Segment trees in this
post of topcoder
To do this question in O(n) time follow the post Segment trees in this
post of topcoder
http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
Here in this given algorithm preprocessing time in O(n) and query time is
O(log n).
--
Akshat Sapra
Under
We can also build a Balanced BST for the window elements and on each shift
we need to have a delete operation and add oeration.
O(n logk)
Also we can add the Shashank algo
where we check if the newly added element is greater than the current BST's
max element.
So we can discard the current BSt
Your algo is good but i don get the part where A[i] (current element) is
less than the first element? Do we enqueue it? And if yes, when the front
element is popped out , how is the next max found in front of the queue?
If you could give an example with the growing queue.
On Friday, 2
@ALL can be solved using segment tree . :-)
On Fri, Sep 2, 2011 at 9:49 AM, Anup Ghatage ghat...@gmail.com wrote:
I just checked Shashank's blog post. The Deque solution is awesome :)
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
Algorithm
Hi Anup , here is naive approach
There is a sliding window of size w which is moving from the very left of
the array to the very right. You can only see the w numbers in the window.
Each time the sliding window moves rightwards by one position.
Following is an example:
The array is [1 3 -1
I made a small program with window size k = 2;
int max(int n, int m)
{
if ( n m )
return n;
else
return m;
}
int main()
{
int arr[8]={3,5,1,9,0,4,-1,7};
int i,j;
for (i=0;i!=j i=7;i++)
for (j=0;j!=i j=7; j++)
{
int k =
I think Dave has already given a good solution in earlier post.
first make a max heap of first k elements and then print max value which is
root .
now add next element in heap and again print max value follow this
procedure till you reach end of an array.
On Fri, Sep 2, 2011 at 9:04 AM, Anup
i think the problem can also be solved by DP..
arr is the original array..
final is the array required..
for(i=0;in;i++) final[i]=arr[i];
for(i=2;i=k;i++)
for(j=0;jn-i+2;j++)
final[i]=max( final[j] , final[j+1]);
initial n-i+2 entries in the array final contains the answer..
time
I just checked Shashank's blog post. The Deque solution is awesome :)
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email
comparison/benchmarks of the
1) naive method, which just calls max with every new index, up to size of
array - k
2) my method , which only makes a call to max if the old max is out of range
or the newest/very rightmost element is greater than max
ruby code:
[image: max_subarray_text.png]
Given an unsorted Array A and any integer k where k = size of A
Print the maximum of each sub-array of size k of A.
eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4
Max: 9 9 9 9 7
--
Anup Ghatage
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
how did u get such o/p for k=4 ?? i dint get plz expalin
On Fri, Sep 2, 2011 at 9:04 AM, Anup Ghatage ghat...@gmail.com wrote:
Given an unsorted Array A and any integer k where k = size of A
Print the maximum of each sub-array of size k of A.
eg: A = [ 3, 5, 1, 9, 0, 4, -1, 7 ] k = 4
13 matches
Mail list logo
