Thread: Maxium sum in a subvecter

Ok well I really have no idea where to begin when it comes to programming this. I'm not looking for someone to write the code for me but I would greatly appreciate a shove in the right direction. I understand what its suppose to do but i dont get how to go about actually doing it. Any help would be greatly apreciated.

thanks in advance





Program 54: Maximum Sum Subvector

A file contains a list of integers. The integers can, and are likely to, contain a mix of positive and negative values. The name of the file comes into your program via argv[1].
The first n numbers of the file are read by your program. The number n comes into your program via argv[2]. The number n will be no greater than 200,000.

For example, the file could contain the values:

-3 100 -4 -2 9 –63 -200 55

Your program will output a number that is the largest sum found in a subvector of this list. In the example above, the output would be 103 since that is the largest sum that can be formed by adding the elements of any subvector.

A subvector can be the entire list, a single member of the list, or it can be any collection of adjacent numbers. If the entire list of numbers contains negative numbers then your program should output 0.

Here is another example: 1 4 3 -4 8
The answer in this case would be 12 since the entire list of numbers forms the maximum sum.

First, figure out how to solve the problem. I give you: 7 -6 4 3 -5 8. You figure out what the answer is. Once you know how to do it, then you can type it into a program.

The easiest, most obvious way is to simply add up all possible length runs of elements and see if the total is the largest it has been.

It's a very interesting problem especially since n is supposed to be up to 200,000. Any naive implementation would give a performance of O(n^2) - or even O(n^3) if you're a real goober - which for such large numbers would take years to execute. I've been mulling it over during the past few days and believe I've finally got an O(n log n) method. I don't think that level of sophistication was asked for in the exercise... but I did find it strange they would cite such a huge number as 200,000.

It is mentioned on the internet that this subvector problem is useful in data-mining and such. Interestingly I haven't stumbled upon a ready-made solution. Just some theories about what the worst case ought to be. So if there are solutions, chances are pretty good they'll be original ones. Just perfect for homework. I ain't tellin'. My brain likes challenges like this occasionally.