Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
July 1st, 2003, 06:46 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation Power: 0
sum of largest sub-sequence in an array

given an array of n elements , how can 1 find the sub-sequence that yields the maximum sum.. Note that negative numbers are
present in the array.

Thanks

#2
July 3rd, 2003, 09:32 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
haha .. theres an o(n^3) algo, an o(n^2) algo, a clever o(nlogn) devide and conquer algo, but theres also a very simple, but very very clever o(n) one.

not givin it to ya though cuz u said i wasn't lazy

heheheheheh
lazy bastard gets the last laugh ... =))

#3
July 3rd, 2003, 11:07 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation Power: 0
hey yogi,
i have figured out the 0(n) and the divide and conquer 1 also.. but the ? is for negative nos.
my algo works only for positive nos.
i can post u my algos if u wish...

#4
July 4th, 2003, 01:43 PM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
yea .. post ur algo and I'll take a look

#5
July 15th, 2003, 01:01 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation Power: 0
aah yogi,
got struck in a couple of other things.. cudnt pay much attention to algo's and my preparation for job-seeking..

my code..
assuming integers in the array...
int localsum = 0;
int globalsum = 0;
for (i = 0; i < n; ++i)
{
localsum +=a[i];

if (localsum > global)
globalsum = localsum;
else if (localsum <0)
localsum = 0;
}

at the end, globalsum will have the largest sum of the sub-sequence
but it doesnt work for nos < 0.

pardon me if u'd problem reading d algo as i prefer to write 'C' style algos.

#6
April 13th, 2004, 05:59 PM
 locopuyo
Registered User

Join Date: Apr 2004
Posts: 1
Time spent in forums: < 1 sec
Reputation Power: 0
How could I turn this into an O(n) alogrithm that looks for 2 integers that add up to a set amount instead of the maximum?

#7
April 16th, 2004, 07:41 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 sec
Reputation Power: 1312
Quote:
 Originally Posted by locopuyo How could I turn this into an O(n) alogrithm that looks for 2 integers that add up to a set amount instead of the maximum?
I'm not sure how to make a guaranteed O(n) algorithm, but an expected O(n) algorithm is easy: go through the array and hash each element into a hash table, and also check if the number you need to add to that number to make it add up the the set amount is in the hash table already. By the time you reach the end of the array, you'll either have some pair that adds to the number, or you'll be sure that there aren't any.

That's not guaranteed to be linear because for practical purposes, hash tables are only expected to have constant time insertion/access performance.

It's surprising that the solution to the original problem of this thread was never posted. I don't think the O(n) algorithm requires any extreme cleverness (don't know what lazy_yogi was going on about )

#8
April 18th, 2004, 09:38 PM
 DaWei_M
Lord of Dorkness

Join Date: Jan 2004
Location: Central New York. Texan via Arizona, out of his element!
Posts: 8,521
Time spent in forums: 4 Weeks 20 h 13 m 16 sec
Warnings Level: 20
Number of bans: 3
Reputation Power: 3268
Well, I wasn't sure I understood the question, because if I did the answer would be trivial. Find the smallest end, the rest is the subsequence with the greatest sum.
__________________
Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
DaWei on Pointers Politically Incorrect.

#9
April 23rd, 2004, 01:07 AM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 sec
Reputation Power: 1312
I took it to mean "given an array A, find indices i, j (i <= j) for which the sum

A[i] + A[i + 1] + A[i + 2] + ... + A[j - 1] + A[j]

is maximized."

#10
August 6th, 2004, 05:22 AM
 basarane
Registered User

Join Date: Aug 2004
Posts: 1
Time spent in forums: < 1 sec
Reputation Power: 0
Simple O(n) algorithm

Yesterday one of my friends ask for a linear algorithm for this problem. I think that the following algorithm solves the problem in linear time. But it should be checked. It is written in php and \$x is the array of numbers and \$n is the number of elements in the array. Array is assumed to be 0-indexed. -9999999999 is used for -Inf and it should be changed with true -Inf constant. \$maxv is the maximum sum and \$maxi1 and \$maxi2 is the start and end indices of the sub-array.

The idea behind the algorithm is as follows:
It uses cumulative sum instead of the original array. Then at each index, it calculates the difference of the value at that index and the smallest value before that index. The maximum sub-array must have this value maximized. Two loops are merged into a single loop. After one pass over the numbers, we have the largest sum and boundary indices of the sub-array. So dynamic programming method is used.

Please check it and let me know if the algorithm is right.

PHP Code:
```  \$mini = -1;     \$minv = 0;     \$maxi1 = 0;     \$maxi2 = 0;     \$maxv = -9999999999;          for (\$i=0;\$i<\$n;\$i++) {         if (\$i>0)             \$x[\$i] += \$x[\$i-1];         if (\$x[\$i]-\$minv>=\$maxv) {             \$maxv = \$x[\$i]-\$minv;             \$maxi1 = \$mini+1;             \$maxi2 = \$i;         }         if (\$x[\$i]<\$minv) {             \$minv = \$x[\$i];             \$mini = \$i;         }     }  ```

#11
April 22nd, 2006, 02:25 PM
 rk_devshed
Registered User

Join Date: Apr 2006
Posts: 1
Time spent in forums: 2 m 39 sec
Reputation Power: 0
thank you basarane for writing such a nice algorithm
you rock!

#12
April 22nd, 2006, 04:07 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 sec
Reputation Power: 1312
I think basarane has left the building, considering he hasn't posted since August 6, 2004.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > sum of largest sub-sequence in an array