Sum

[ahmed9300]

Hello everybody!
I have a problem : I don't know how to create an algorithm that takes n numbers of a list (a_1;...a_n) and return the two numbers i,j that verifies 0=<i<j=<n and the maximum sum (from i to j) : For instance the list (-1,1,1,-1) returns the sum=2 with i=2 and j=3.
Help!

[simeonz]

The maximum sum is the result from adding the largest and next to largest number in the array. Demonstrating this is not so hard. To find the forementioned numbers you need to use the following algo:

if the first element in the array is greater than the second
the first element becomes the current largest number
the second element becomes the current next to largest number
else
the first element becomes the current next to largest number
the second element becomes the current largest number

for each element in the array after the second
if the element is greater than the largest number so far
the largest number so far becomes the new next to largest number
the current element becomes the new largest number

Of course, you have to track (record) not only the values, but also the indexes for the two largest numbers you have found.

Regards

EDIT: This is all assuming that you need to create your own algorithm. Otherwise, you can always use the nth_element routine. It can position the two largest elements at the beginning of the array for you. (It will be slower in this particular case.) Ask about it, if you think that you are permitted to directly apply STL for the solution.
http://www.cplusplus.com/reference/algorithm/nth_element/

[ahmed9300]

Hello simeonz!

Thank you for having answered me so quickly.I will try this and I let you know.

All the best.

[ne555]

and the maximum sum (from i to j)

do you sum the range?

[simeonz]

+1 ne555
If you want the maximum sum for the entire range, not just the maximum sum of two numbers then my algorithm is pure garbage. Will come back to this.

[simeonz]

Ok. Let me apologize again for misleading you. This is much harder problem. Let's first start with the naive algorithm:

max_sum = value at index 0
For every index i > 0
  For every index j <= i
    Compute sum(i, j)
    If sum(i, j) > current max_sum
      new max_sum = sum(i, j)

The problem with this algorithm is that it has complexity Theta(n^3), which makes it unusable for larger inputs. A slightly improved version has complexity Theta(n^2), but I am going to present to you alternative that has complexity Theta(n), which is optimal for any problem whose solution depends on the entire input:

max_sum = value at index 0
max_suffix_sum = value at index 0
For every index i > 0
  If max_suffix_sum > 0
    max_suffix_sum = max_suffix_sum + value at index i
  else
    max_suffix_sum = value at index i
  If max_suffix_sum > max_sum
    max_sum = max_suffix_sum

The latter algorithm is based on two observations:

1) The "maximum sum" subsequence of {a_i: i = 0..n} is either the same as the "maximum sum" subsequence of {a_i: i = 0..n-1} or is some subsequence that ends with a_n (i.e. a "suffix")

2) The sum over two adjacent subsequences is larger than the second of them iff the the first of them is positive. That is, the sum over {a_i: i = 0..n} is greater than the sum over {a_i: i = j..n, j > 0} if and only if the sum over {a_i: i = 0..j-1} is positive. For the algorithm, the case j=n is used particularly.

Please ask if you have questions. I wasn't careful enough. My bad.

Regards