here is the solution of O(n) ...
int maxSubArray(int array[],int n) // n is the length of the given array
...
{
int left=0,right=0; // these are to indicate the subscript range on which
we got the max array ..
int temp_left=0;
int max=0,sum=0;
for(int i=0;i<n;i++)
{
sum += array[i];
if(max<sum)
{
max=sum;
right=i;
left=temp_left;
}
if(sum<0) // if the sum is negative ..
{
sum=0;
temp_left=i+1;
}
}
return max;
}
This'll work ....
On Sun, Sep 4, 2011 at 4:54 AM, tarun kumar <[email protected]> wrote:
> the problem can be solved in O(n) time without using extra space .using the
> algorithm of "finding the subarray of maximum sum in a given array."(time
> complexity is O(n) and no extra space).
> here you just have to stop when you find sum equal to k.
>
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
*
Mobile +91 8056127652*
<[email protected]>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
