@ashish:
what if the array is {-2,3,4,17,-8,9}?
On Wed, Sep 8, 2010 at 8:52 AM, Anand <[email protected]> wrote:
> Maximum Value Contiguous Subsequence problem in O(n).
> http://codepad.org/BhYxSlp4
>
>
> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal <
> [email protected]> wrote:
>
>> yeah..it will be i=j+1;
>> it was misprinted
>>
>>
>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj <[email protected]>wrote:
>>
>>> In the else if condition, the increment of the end index i should be
>>> i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
>>> Kadane's algo :
>>> http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
>>>
>>> On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal <
>>> [email protected]> wrote:
>>>
>>>> int max=0,sum=0,begin=0,end=0,i=0;
>>>> for(int j=0 to n){
>>>> sum+=a[j];
>>>> if(max<sum){
>>>> max=sum;
>>>> begin=i;
>>>> end=j;
>>>> }
>>>> else if(sum<0){
>>>> i=j+i;
>>>> sum=0;
>>>> }
>>>>
>>>> return sum;
>>>> i will tell the starting index and j will tell ending index;
>>>> o(n);
>>>> correct me if i am wrong
>>>>
>>>>
>>>>
>>>> On Mon, Sep 6, 2010 at 1:42 PM, bittu <[email protected]>wrote:
>>>>
>>>>> Given a sequence of integers, find a continuous subsequence which
>>>>> maximizes the sum of its elements, that is, the elements of no other
>>>>> single subsequence add up to a value larger than this one. An empty
>>>>> subsequence is considered to have the sum 0; thus if all elements are
>>>>> negative, the result must be the empty sequence.
>>>>>
>>>>>
>>>>> Solution:O(n^2) i want O(nlogn).......???????????????????
>>>>>
>>>>>
>>>>>
>>>>> #include <stdio.h>
>>>>> #include<conio.h>
>>>>> #include<iostream.h>
>>>>> #include<stdlib.h>
>>>>> int main()
>>>>> {
>>>>> int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
>>>>> int length = 11;
>>>>>
>>>>> int begin, end, beginmax, endmax, maxsum, sum, i;
>>>>>
>>>>> sum = 0;
>>>>> beginmax = 0;
>>>>> endmax = -1;
>>>>> maxsum = 0;
>>>>>
>>>>>
>>>>> for (begin=0; begin<length; begin++) {
>>>>> sum = 0;
>>>>> for(end=begin; end<length; end++) {
>>>>> sum += a[end];
>>>>> if(sum > maxsum) {
>>>>> maxsum = sum;
>>>>> beginmax = begin;
>>>>> endmax = end;
>>>>> }
>>>>>
>>>>> }
>>>>> cout<<sum<<"\t";
>>>>> }
>>>>> cout<<endl;
>>>>> for(i=beginmax; i<=endmax; i++) {
>>>>> printf("%d\n", a[i]);
>>>>> }
>>>>>
>>>>> getch();
>>>>> }
>>>>>
>>>>>
>>>>> its has time complexity O(n^2) ..does better solution exist
>>>>>
>>>>> --
>>>>> 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]<algogeeks%[email protected]>
>>>>> .
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>> --
>>>> 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]<algogeeks%[email protected]>
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Sahana Gururaj
>>>
>>>
>>> --
>>> 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]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> 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]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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.
