@ Gaurav
I don't think the above nlogn approach will work. If i m not wrong,
the above nlogn approach is a modification of the nlogn algo for
maximum continuous subset problem.
I have a doubt with the crossing subarray solution. I see that your if
and while loop breaks out if totalsum =K is not
My implementation, can anyone offer my test cases that i can verify?
struct Deal
{
unsigned int nStartIndex;
unsigned int nEndIndex;
unsigned int nSum;
Deal()
{
nStartIndex = 0;
nEndIndex = 0;
nSum = 0;
}
};
int findBestDeal( const
@ giridhar IS
assuming u wanted k=13 ( max sum =13)
start : i,j points to 1st element
keep a track of sum between i to j
outer loop: till ja.length
sum=sum+a[j]
inner loop till sum exceeds k.
increment i .
@ giridhar IS correction missed increment j in outer loop: sry :-)
assuming u wanted k=13 ( max sum =13)
start : i,j points to 1st element
keep a track of sum between i to j
outer loop: till ja.length
sum=sum+a[j]
increment j
inner loop
@ sourabh :-) yep, got your point... it wont work for all cases.
but
if we set initial max to a negative value . say max possible 64 bit
-ve number.then ?
point is though the code has limitations it will work fine mostly.
On 12/5/11, sourabh sourabhd2...@gmail.com wrote:
@sourabh singh..
Hey
@sourabh
can you explain me how it will work for this example
a[]={2,7,3,4,5,8,10}
On Dec 7, 12:17 am, sourabh singh singhsourab...@gmail.com wrote:
@ sourabh :-) yep, got your point... it wont work for all cases.
but
if we set initial max to a negative value . say max possible 64 bit
@sourabh..
I don't think it will work for all the cases.. did u consider negative
integers as well... what i can understand from the above code is that
u have taken 2 pointers of which one points to the beginning of the
subarray and other one at the end of the subarray and u r shifting the
@ sourabh tried some cases its working on -ve as well. pls post some
case in which it might not work.
On 12/5/11, sourabh sourabhd2...@gmail.com wrote:
@sourabh..
I don't think it will work for all the cases.. did u consider negative
integers as well... what i can understand from the above
@sourabh
i guess you need to modify this statement :-
3) Now for each element B[i][0] , do a (modified) binary *search for
the closest value smaller than equal to (X + B[i][0])* in array B[i
+1... n][0] ,
Say the found index after binary search is j ( which is i)...
12 + 2 = 12 , closest
and you made mistake above in calculating 12 + 2 = *12* , its 14
12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 , i
= 1, j = 4
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i
= 2, j = 4
12 + 6 = 18 , closest element found = 15 , closest to X = 15
@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
i = 3, j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
=5 , i = 4, j = 4
yup i made some calculation error
Now this algo works perfectly :) :)
Thanks for your help and explanation :) :)
On Thu, Dec 1, 2011 at 4:26 PM, sourabh sourabhd2...@gmail.com wrote:
@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 =
@atul...
thanks dude for ur thorough screening of the algo and pointing out the
mistakes... I think that's y its always said that until and unless we
don't turn an algo to a working code we are never really sure whether
its perfect and covers all the cases.
On Dec 1, 4:23 pm, atul anand
A little variation of kadane's algo will do as written below: -
#include stdafx.h
#include stdlib.h
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = {-1,3,1,2,-3};
int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0 ,
endIndex = 0, itr = 0;
int k=12;
@ankit : sorry dude , its not working for given input
{2,1,3,4,5} k=12,
ans=12, sub-array={3,4,5}
your algo will give ans=10 sub-array{0 to 3}
On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha akki12...@gmail.com wrote:
A little variation of kadane's algo will do as written below: -
#include
@ankit...
I don't think the algorithm is correct...
The check max_ending_here 0 max_limit_here =k doesn't look
correct...
Also I am not able to figure out the importance of 0 in the check ..
Ankit, may be I am wrong. Hence, can you come up with the algorithm
explaining ( with a set of steps )
Given array of integers A[n],
create an array B[n] such that B[i] = sum of all elements from A[1]
to A[i],
Now sort array B, and for each element B[i] ( smaller that equal to
X), do a (modified) binary search for the closest value smaller than
equal to (X - B[i]) in array B[i+1... n]
Keep
Given array of integers A, create an 2-d array B of size n*2 such
that B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
sort array B based on B[i][0]..
Now for each element B[i][0] ( till its smaller that equal to X), do a
(modified) binary search for the closest value smaller
@sourabh : please let me know where i am making mistake in understanding
your algo:-
considering your 1st algo:-
1) Given array of integers A[n], = {2,1,3,4,5}
2) create an array B[n] such that B[i] = sum of all elements from A[1]
to A[i], // i guess it should be A[0] to A[i]
Array B formed
First i would like to rectify a editing mistake that is as foolws :
Say the found index after binary search is j ( which is i)..
Now if B[i][1] B[j][1] then keep track of the max no. closest to X
( that is B[i][0] + B[j][0])... // earlier the last text was B[i][1] +
B[j][1]
Now to clarify your
I am rewriting the algo here in much more readable form :
Given array of integers A,
1) Create an 2-d array B[n][2] of size n*2 such that
a) B[i][0] = sum of all elements from A[0] to A[i],
b) B[i][1] = i
2) Sort array B based on B[i][0] i.e. sort array B[][0] and
correspondingly
@sourabh :
*Cumulative SUM*
*i*
2
0
3
1
6
2
10
3
15
4
above will the array B[][] formed for array A[]={ 2,1,3,4,5 }
let X=12;
12 - 2 = 10 , closest element found = 10 , *closest to X = 2 + 10 =12*
,*i = 0 , j = 3
* // this is the answer , so i am calculating other
max
@atul.. thanks for pointing out.. i m doing a small mistake in
calculating closest element found... and i have rectified it below...
Also i have missed a corner case in the above solution hence i m
putting it down here...
3a) Corner case: Do modified binary search for closest element smaller
than
23 matches
Mail list logo
