13,833,837 members
See more:
Given an array of integers - some positive, some negative, some neither, find the set of consecutive numbers in this array with the largest possible sum.

Obviously if all the numbers are positive the answer is the initial array. If all are negative then the answer is an empty array. The in-between case is the interesting one.
Posted
Updated 6-Feb-17 2:06am
Patrice T 3-Feb-17 21:35pm

"find the set of consecutive numbers in this array with the largest possible sum."
I think it don't imply that the result have to be positive.
PIEBALDconsult 3-Feb-17 23:23pm

I agree. Maybe he meant "positive"?
PIEBALDconsult 3-Feb-17 23:23pm

Pffft. Arrays are sooo last millenium.
Yet this sounds familar. As if it has been asked here before...

https://www.codeproject.com/Messages/5100662/LENGTH-of-the-maximum-contiguous-sum.aspx
https://leetcode.com/problems/maximum-subarray/

Graeme_Grant 4-Feb-17 5:40am

What happened to last week's challenge? I am surprised that no one other than myself attempted it and no winner was announced.
PIEBALDconsult 4-Feb-17 10:50am

I did, but in C#. I guess I can post it anyway.
Done.
Graeme_Grant 4-Feb-17 19:04pm

Yes, my C# prototype was easy to do and maybe that is why it wasn't allowed.
PIEBALDconsult 4-Feb-17 19:17pm

Probably.
PIEBALDconsult 4-Feb-17 11:44am

What should be the result of
5 -5 5 -10 5 -5 5
?

Or even:
5 -5 5 -5 5
?
Graeme_Grant 4-Feb-17 19:02pm

[5] would be the answer for both
PIEBALDconsult 4-Feb-17 19:18pm

No, it's asking for an array, not the sum.
Graeme_Grant 4-Feb-17 19:21pm

yes, the brackets represent an array with one element, no brackets would be the sum. ;)
PIEBALDconsult 4-Feb-17 19:24pm

But there are more subarrays that sum to 5 in there.
Graeme_Grant 4-Feb-17 19:26pm

so are you saying that the answer should be an array of arrays that meet the criteria? I did ponder that...
Patrice T 4-Feb-17 20:24pm

Graeme_Grant 4-Feb-17 20:30pm

It asks for a singular result, but I added a version that can handle multiples as that is a possibility.
Graeme_Grant 4-Feb-17 20:29pm

For [5, -5, 5, -10, 5, -5, 5], there are multiple sets
... the largest group is [5] with a sum of 5
... the largest group is [5, -5, 5] with a sum of 5
... the largest group is [5] with a sum of 5
... the largest group is [5] with a sum of 5

For [5, -5, 5, -5, 5], there are multiple sets
... the largest group is [5] with a sum of 5
... the largest group is [5, -5, 5] with a sum of 5
... the largest group is [5] with a sum of 5
Patrice T 4-Feb-17 20:35pm

"For [5, -5, 5, -5, 5], there are multiple sets"
does it miss
... the largest group is [5, -5, 5, -5, 5] with a sum of 5
?
Graeme_Grant 4-Feb-17 21:08pm

Good catch! Now correctly handles all cases for both versions. :)
PIEBALDconsult 4-Feb-17 20:58pm

Right on. (Both of you.)
In my opinion (though not in my implementation), there may be multiple result sets.
The question from 2015-07 asked for the longest subarray, but there may yet be more than one suitable result set.
Graeme_Grant 4-Feb-17 21:20pm

Here is another set to test against: [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2]

There are 3 possible answers, each different.
Bryian Tan 4-Feb-17 21:30pm

Geezzz. You guy are like a mad Math scientist here. In a good way :)
PIEBALDconsult 4-Feb-17 22:53pm

Pedants. The word is pedants. (He said pedantically.)
Graeme_Grant 4-Feb-17 23:24pm

Devil is in the details... ;)

## Solution 4

Here is another quick one:

```using System;
using System.Collections.Generic;
using System.Linq;

namespace LargestGroupSum
{
static class Program
{
static void Main(string[] args)
{
foreach (var test in new List<List<int>>()
{
new List<int>(),
new List<int>() { -1, -2, -5, -4, -5, -1, -2, -11 },
new List<int>() { 1, 2, 5, 4, 5, 1, 2, 11 },
new List<int>() { 1, 2, -5, 4, 5, -1, 2, -11 },
new List<int>() { 1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2 },
new List<int>() { 5, -5, 5, -10, 5, -5, 5 },
new List<int>() { 5, -5, 5, -5, 5 },
new List<int>() { 5, 5, -5, -6 },
new List<int>() { -1, -1, 1, -1, 2 }
})
{
var lg = test.LargestGroupSumList();
Console.WriteLine(\$"For [{string.Join(",", test)}], the largest group is [{string.Join(",", lg)}] with {(lg.Any() ? \$"a sum of {lg.Sum()}" : "no value")}");
}
Console.WriteLine("\r\n-- Press any key to exit --");
}
}

public static class HelperExtensions
{
public static IList<int> LargestGroupSumList(this IList<int> list)
{
if (!list.Any(x => x >= 1))
return new List<int>();
else if (!list.Any(x => x < 1))
return list;
else
{
var groups = new List<List<int>>();
for (int i = 0; i < list.Count; i++)
for (int j = 0; j < list.Count - i; j++)
return groups.OrderByDescending(X => X.Count).OrderByDescending(x => x.Sum()).First();
}
}
}
}```

```Imports System.Runtime.CompilerServices

Module Module1

Sub Main()
For Each test In New List(Of List(Of Integer))() From {
New List(Of Integer)(),
New List(Of Integer)() From {-1, -2, -5, -4, -5, -1, -2, -11},
New List(Of Integer)() From {1, 2, 5, 4, 5, 1, 2, 11},
New List(Of Integer)() From {1, 2, -5, 4, 5, -1, 2, -11},
New List(Of Integer)() From {1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2},
New List(Of Integer)() From {5, -5, 5, -10, 5, -5, 5},
New List(Of Integer)() From {5, -5, 5, -5, 5},
New List(Of Integer)() From {5, 5, -5, -6},
New List(Of Integer)() From {-1, -1, 1, -1, 2}}
Dim lg = test.LargestGroupSumList()
Console.WriteLine("For [{0}], the largest group is [{1}] with {2}", String.Join(",", test), String.Join(",", lg), If(lg.Any(), String.Format("a sum of {0}", lg.Sum()), "no value"))
Next
Console.WriteLine("{0}-- Press any key to exit --", vbCrLf)
End Sub
End Module

Public Module HelperExtensions
<Extension>
Public Function LargestGroupSumList(list As IList(Of Integer)) As IList(Of Integer)
If Not list.Any(Function(x) x >= 1) Then
Return New List(Of Integer)()
ElseIf Not list.Any(Function(x) x < 1) Then
Return list
Else
Dim groups = New List(Of List(Of Integer))()
For i As Integer = 0 To list.Count - 1
For j As Integer = 0 To list.Count - i - 1
Next
Next
Return groups.OrderByDescending(Function(x) x.Count).OrderByDescending(Function(x) x.Sum()).First()
End If
End Function
End Module```

Outputs:
```For [], the largest group is [] with no value
For [-1,-2,-5,-4,-5,-1,-2,-11], the largest group is [] with no value
For [1,2,5,4,5,1,2,11], the largest group is [1,2,5,4,5,1,2,11] with a sum of 31
For [1,2,-5,4,5,-1,2,-11], the largest group is [4,5,-1,2] with a sum of 10
For [1,2,4,-20,4,2,1,-15,3,2,2], the largest group is [1,2,4] with a sum of 7
For [5,-5,5,-10,5,-5,5], the largest group is [5,-5,5] with a sum of 5
For [5,-5,5,-5,5], the largest group is [5,-5,5,-5,5] with a sum of 5
For [5,5,-5,-6], the largest group is [5,5] with a sum of 10
For [-1,-1,1,-1,2], the largest group is [1,-1,2] with a sum of 2

-- Press any key to exit --```

And you can run it online[^]

Update
Here is another version that handles multiple return sets that are equally the largest possible sum of consecutive numbers.

```using System;
using System.Collections.Generic;
using System.Linq;

namespace LargestGroupSum
{
static class Program
{
static void Main(string[] args)
{
Console.WriteLine("Largest possible sum of consecutive numbers");
Console.WriteLine("===========================================");
foreach (var test in new List<List<int>>()
{
new List<int>(),
new List<int>() { -1, -2, -5, -4, -5, -1, -2, -11 },
new List<int>() { 1, 2, 5, 4, 5, 1, 2, 11 },
new List<int>() { 1, 2, -5, 4, 5, -1, 2, -11 },
new List<int>() { 1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2 },
new List<int>() { 5, -5, 5, -10, 5, -5, 5 },
new List<int>() { 5, -5, 5, -5, 5 },
new List<int>() { 5, 5, -5, -6 },
new List<int>() { -1, -1, 1, -1, 2 }
})
{
var results = test.LargestGroupSumList();
Console.WriteLine(\$"\r\nFor [{string.Join(", ", test)}], there {(results.Count() > 1 ? "are multiple sets" : results.FirstOrDefault() == null ? "are no sets" : "is one set")}");
foreach (var lg in results)
if (lg != null) Console.WriteLine(\$"... the largest group is [{string.Join(", ", lg)}] with a sum of {lg.Sum()}");
}
Console.WriteLine("\r\n-- Press any key to exit --");
}
}

public static class HelperExtensions
{
public static IEnumerable<IList<int>> LargestGroupSumList(this IList<int> list)
{
if (!list.Any(x => x >= 1))
yield return null;
else if (!list.Any(x => x < 1))
yield return list;
else
{
var groups = new List<List<int>>();
for (int i = 0; i < list.Count; i++)
for (int j = 0; j < list.Count - i; j++)

var results = groups.OrderByDescending(X => X.Count).OrderByDescending(x => x.Sum()).ToList();
int sum = results.First().Sum(), count = results.First().Count;
foreach (var item in results)
if (item.Sum().Equals(sum) && item.Count.Equals(count)) yield return item;
}
}
}
}```

```Imports System.Runtime.CompilerServices

Module Module1

Sub Main()
Console.WriteLine("Largest possible sum of consecutive numbers")
Console.WriteLine("===========================================")
For Each test In New List(Of List(Of Integer))() From {
New List(Of Integer)(),
New List(Of Integer)() From {-1, -2, -5, -4, -5, -1, -2, -11},
New List(Of Integer)() From {1, 2, 5, 4, 5, 1, 2, 11},
New List(Of Integer)() From {1, 2, -5, 4, 5, -1, 2, -11},
New List(Of Integer)() From {1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2},
New List(Of Integer)() From {5, -5, 5, -10, 5, -5, 5},
New List(Of Integer)() From {5, -5, 5, -5, 5},
New List(Of Integer)() From {5, 5, -5, -6},
New List(Of Integer)() From {-1, -1, 1, -1, 2}
}
Dim results = test.LargestGroupSumList()
Console.WriteLine("{0}For [{1}], there {2}", vbCrLf, String.Join(", ", test), (If(results.Count > 1, "are multiple sets", If(results.FirstOrDefault() Is Nothing, "are no sets", "is one set"))))
For Each lg In results
If lg IsNot Nothing Then
Console.WriteLine("... the largest group is [{0}] with a sum of {1}", String.Join(", ", lg), lg.Sum())
End If
Next
Next
Console.WriteLine("{0}-- Press any key to exit --", vbCrLf)
End Sub

End Module

Public Module HelperExtensions
<Extension>
Public Iterator Function LargestGroupSumList(list As IList(Of Integer)) As IEnumerable(Of IList(Of Integer))
If Not list.Any() OrElse Not list.Any(Function(x) x > 1) Then
Yield Nothing
ElseIf Not list.Any(Function(x) x < 1) Then
Yield list
Else
Dim groups = New List(Of List(Of Integer))()
For i As Integer = 0 To list.Count - 1
For j As Integer = 0 To list.Count - i - 1
Next
Next

Dim results = groups.OrderByDescending(Function(x) x.Count).OrderByDescending(Function(x) x.Sum()).ToList()
Dim sum As Integer = results.First().Sum(), count As Integer = results.First().Count
For Each item In results
If item.Sum().Equals(sum) AndAlso item.Count.Equals(count) Then
Yield item
End If
Next
End If
End Function
End Module```

Outputs:
```Largest possible sum of consecutive numbers
===========================================

For [], there are no sets

For [-1, -2, -5, -4, -5, -1, -2, -11], there are no sets

For [1, 2, 5, 4, 5, 1, 2, 11], there is one set
... the largest group is [1, 2, 5, 4, 5, 1, 2, 11] with a sum of 31

For [1, 2, -5, 4, 5, -1, 2, -11], there is one set
... the largest group is [4, 5, -1, 2] with a sum of 10

For [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2], there are multiple sets
... the largest group is [1, 2, 4] with a sum of 7
... the largest group is [4, 2, 1] with a sum of 7
... the largest group is [3, 2, 2] with a sum of 7

For [5, -5, 5, -10, 5, -5, 5], there are multiple sets
... the largest group is [5, -5, 5] with a sum of 5
... the largest group is [5, -5, 5] with a sum of 5

For [5, -5, 5, -5, 5], there is one set
... the largest group is [5, -5, 5, -5, 5] with a sum of 5

For [5, 5, -5, -6], there is one set
... the largest group is [5, 5] with a sum of 10

For [-1, -1, 1, -1, 2], there is one set
... the largest group is [1, -1, 2] with a sum of 2

-- Press any key to exit --```

And you can run it online[^]

Update #2
Looking at the extension method, I felt that I could reduce it from 12 lines of code into 1 using Linq! Here is the new single-line (split onto multiple lines to avoid wrapping) extension method using Linq Method Syntax:

```public static List<List<int>> LargestGroupSumList(this List<int> list)
=> !list.Any(x => x >= 1) ? new List<List<int>>() :
!list.Any(x => x < 1) ? new List<List<int>>() { list } :
Enumerable.Range(0, list.Count).SelectMany(x =>
Enumerable.Range(1, list.Count - x).Select(y =>
list.Skip(x).Take(y).ToList()))
.OrderByDescending(x => x.Sum()).ThenByDescending(x => x.Count)
.GroupBy(x => x.Sum()).First()
.GroupBy(x => x.Count).First().ToList();```

```<Extension>
Public Function LargestGroupSumList(list As List(Of Integer)) As List(Of List(Of Integer))
Return If(Not list.Any(Function(x) x >= 1), New List(Of List(Of Integer))(),
If(Not list.Any(Function(x) x < 1), New List(Of List(Of Integer))() From {list},
Enumerable.Range(0, list.Count).SelectMany(Function(x) _
Enumerable.Range(1, list.Count - x).[Select](Function(y) _
list.Skip(x).Take(y).ToList())) _
.OrderByDescending(Function(x) x.Sum()) _
.ThenByDescending(Function(x) x.Count) _
.GroupBy(Function(x) x.Sum()).First() _
.GroupBy(Function(x) x.Count).First().ToList()))
End Function```

And here is the Linq Query Syntax version (again: split onto multiple lines to avoid wrapping):

```public static List<List<int>> LargestGroupSumList(this List<int> list)
=> !list.Any(x => x >= 1) ? new List<List<int>>() :
!list.Any(x => x < 1) ? new List<List<int>>() { list } :
(from gs in (from x in Enumerable.Range(0, list.Count)
from y in Enumerable.Range(1, list.Count - x)
let r = list.Skip(x).Take(y).ToList()
orderby r.Sum() descending, r.Count descending
group r by r.Sum()).First()
group gs by gs.Count).First().ToList();```

```<Extension>
Public Function LargestGroupSumList(list As List(Of Integer)) As List(Of List(Of Integer))
Return If(Not list.Any(Function(x) x >= 1), New List(Of List(Of Integer))(),
If(Not list.Any(Function(x) x < 1), New List(Of List(Of Integer))() From {list},
(From x In (From x In
(From x In Enumerable.Range(0, list.Count)
From y In Enumerable.Range(1, list.Count - x)
Let r = list.Skip(x).Take(y).ToList()
Order By r.Sum() Descending, r.Count Descending
Group By r.Sum() Into gs = Group).First().gs
Group By x.r.Count() Into gc = Group).First().gc
Select x.r).ToList()))
End Function```

You can read more about the two Linq syntaxes in the Query Syntax and Method Syntax in LINQ (C#)[^] article on MSDN.

Note: If only a single result is required, then simply request it from the returned list:
`test.LargestGroupSumList().FirstOrDefault()`
v24
PIEBALDconsult 4-Feb-17 10:58am

I disagree with an empty array summing to zero.
Graeme_Grant 4-Feb-17 19:12pm

We are only supposed to return an array, but showing the sum value is a bonus. You could use this output instead:
`Console.WriteLine(\$"For [{string.Join(",", test)}], the largest group is [{string.Join(",", lg)}] with {(lg.Any() ? \$"a sum of {lg.Sum()}" : "no value")}");`
Graeme_Grant 4-Feb-17 20:16pm

Added an update that has no sum for empty results and now handles multiple sets that have the largest possible sum.
Bryian Tan 4-Feb-17 21:27pm

What should be the answer for [5,5,-5,-6]?
Graeme_Grant 4-Feb-17 21:31pm

```For [5, 5, -5, -6], there is one set
... the largest group is [5, 5] with a sum of 10```
Graeme_Grant 4-Feb-17 21:35pm

There are links above in this solution where you can input your own numbers and test. :)
Graeme_Grant 4-Feb-17 21:27pm

Rather than update the solution, here is another test set with results:
```For [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2], there are multiple sets
... the largest group is [1, 2, 4] with a sum of 7
... the largest group is [4, 2, 1] with a sum of 7
... the largest group is [3, 2, 2] with a sum of 7```
Bryian Tan 4-Feb-17 21:39pm

more question :) {9,-2,8,-1,-6} , why the largest group is [9,-2,8], i though it need to be a consecutive numbers
Graeme_Grant 4-Feb-17 22:00pm

Consecutive (one after another) not incremental.
Bryian Tan 4-Feb-17 22:14pm

Got it. Thanks.
Richard Deeming 7-Feb-17 12:57pm

`!list.Any() || !list.Any(x => x > 1) ? ... : !list.Any(x => x < 1) ? ... : ...`

How many times are you going to iterate over that list? :P

You can certainly remove the first call to `Any` - if there are no elements in the list, there will also be no elements greater than 1 in the list.

It might also be easier to follow the logic if you replace `!list.Any(condition)` with `list.All(!condition)`:
`list.All(x => x <= 1) ? ... : list.All(x => x >= 1) ? ... : ...`

That makes it immediately obvious that the first condition should be `list.All(x => x < 1)`, not `list.All(x => x <= 1)`.
(So your version should be: `!list.Any(x => x >= 1)`)

`.OrderByDescending(x => x.Count).OrderByDescending(x => x.Sum())`

Calling `OrderBy[Descending]` negates any previous ordering. You should either remove the first `OrderByDescending` call, or change the second one to `ThenByDescending` if you want to sort by two different criteria.
Graeme_Grant 7-Feb-17 15:13pm

I've made some changes that reflect some of the suggestions made. Thanks! :)

## Solution 1

```private int getMaxSubArray(int[] a, out int sIndex, out int eIndex)
{
int maxSoFar = int.MinValue;
int maxEndingHere = 0;
sIndex = 0;
eIndex = 0;
for (int i = 0; i < a.Length; i++)
{
maxEndingHere = maxEndingHere + a[i];
if (maxSoFar < maxEndingHere)
{
maxSoFar = maxEndingHere;
eIndex = i;
}
if (maxEndingHere < 0)
{
maxEndingHere = 0;
sIndex = i + 1;
}
}
return maxSoFar;
}
```
PIEBALDconsult 4-Feb-17 14:35pm

Does that satisfy the specification "find the set of consecutive numbers ... the answer is an ... array" ?
Graeme_Grant 4-Feb-17 21:56pm

I ran the code and found a few issues (besides not returning arrays): [] is not handled and throws an error, and most of the tests fail. here are the tests online[^]

## Solution 2

A quick one to join the heat:
```def largestSummedConsecutiveSubArray(integer_list):
running_sum = 0
result_lists = []
temp_list = []
for integer in integer_list:
running_sum = running_sum + integer
if running_sum >= 0:
temp_list.append(integer)
else:
result_lists.append(temp_list)
temp_list = []
running_sum = 0

if len(temp_list) > 0:
result_lists.append(temp_list)

largest_summed_consecutive_subArray = []

max_sum = 0
for i in result_lists:
if sum(i) > max_sum:
max_sum = sum(i)
largest_summed_consecutive_subArray = i

return largest_summed_consecutive_subArray

#integer_list = []
#integer_list = [-1, -2, -5, -4, -5, -1, -2, -11]
#integer_list = [1, 2, 5, 4, 5, 1, 2, 11]
integer_list = [1, 2, -5, 4, 5, -1, 2, -11]

largest_summed_consecutive_subArray = largestSummedConsecutiveSubArray(integer_list)

print('For the original integer array of {}'.format(integer_list))
print('The largest summed consecutive sub array is {} with a sum of {}.'.format(largest_summed_consecutive_subArray, sum(largest_summed_consecutive_subArray)))```

The outputs:
```For the original integer array of []
The largest summed consecutive sub array is [] with a sum of 0.

For the original integer array of [-1, -2, -5, -4, -5, -1, -2, -11]
The largest summed consecutive sub array is [] with a sum of 0.

For the original integer array of [1, 2, 5, 4, 5, 1, 2, 11]
The largest summed consecutive sub array is [1, 2, 5, 4, 5, 1, 2, 11] with a sum of 31.

For the original integer array of [1, 2, -5, 4, 5, -1, 2, -11]
The largest summed consecutive sub array is [4, 5, -1, 2] with a sum of 10.```
Play it online[^].

+++++[Round 2]+++++
Thank you to Bryian Tan for testing and pointing out the bug. It seems that the preceding code breaks when a negative integer is being included as a last element in the potential solution array. So the fix is to remove this negative integer if it is present as last element in the potential solution array. For that, a function is created for this:
```# Remove last element if negative from a list
def removeLastNegativeFromList(aList):
for t in reversed(aList):
if t > 0:
break
else:
aList.remove(t)
return aList

def largestSummedConsecutiveSubArray(integer_list):
running_sum = 0
result_lists = []
temp_list = []
for integer in integer_list:
running_sum = running_sum + integer
if running_sum >= 0:
temp_list.append(integer)
else:
temp_list = removeLastNegativeFromList(temp_list)
result_lists.append(temp_list)
temp_list = []
running_sum = 0

if len(temp_list) > 0:
temp_list = removeLastNegativeFromList(temp_list)
result_lists.append(temp_list)

largest_summed_consecutive_subArray = []

max_sum = 0
for i in result_lists:
if sum(i) > max_sum:
max_sum = sum(i)
largest_summed_consecutive_subArray = i

return largest_summed_consecutive_subArray

#integer_list = []
#integer_list = [-1, -2, -5, -4, -5, -1, -2, -11]
#integer_list = [1, 2, 5, 4, 5, 1, 2, 11]
#integer_list = [1, 2, -5, 4, 5, -1, 2, -11]
#integer_list = [5,5,-3,-6]
#integer_list = [5,5,-5,-6]
integer_list = [5,5,-8,-6]

largest_summed_consecutive_subArray = largestSummedConsecutiveSubArray(integer_list)

print('For the original integer array of {}'.format(integer_list))
print('The largest summed consecutive sub array is {} with a sum of {}.'.format(largest_summed_consecutive_subArray, sum(largest_summed_consecutive_subArray)))```

Demo and testing at Coding challenge: largest possible sum from consecutive numbers v2, Python 3 - rextester[^]

+++++[Round 3]+++++
As pointed out by Graeme_Grant, there could be multiple occurrences of sub arrays that satisfy the largest sum, so I have modified the part of the code to take into such scenario:
```largest_summed_consecutive_subArray = result_lists[:]

for i in largest_summed_consecutive_subArray:
for j in result_lists:
if sum(i) < sum(j):
largest_summed_consecutive_subArray.remove(i)
break```

The resultant code is
```# Remove last element if negative from a list
def removeLastNegativeFromList(aList):
for t in reversed(aList):
if t > 0:
break
else:
aList.remove(t)
return aList

def largestSummedConsecutiveSubArray(integer_list):
running_sum = 0
result_lists = []
temp_list = []
for integer in integer_list:
running_sum = running_sum + integer
if running_sum >= 0:
temp_list.append(integer)
else:
temp_list = removeLastNegativeFromList(temp_list)
result_lists.append(temp_list)
temp_list = []
running_sum = 0

if len(temp_list) > 0:
temp_list = removeLastNegativeFromList(temp_list)
result_lists.append(temp_list)

largest_summed_consecutive_subArray = result_lists[:]

for i in largest_summed_consecutive_subArray[:]: # fixed this!
for j in result_lists:
if sum(i) < sum(j):
largest_summed_consecutive_subArray.remove(i)
break
return largest_summed_consecutive_subArray

#integer_list = []
#integer_list = [-1, -2, -5, -4, -5, -1, -2, -11]
#integer_list = [1, 2, 5, 4, 5, 1, 2, 11]
#integer_list = [1, 2, -5, 4, 5, -1, 2, -11]
#integer_list = [5,5,-3,-6]
#integer_list = [5,5,-5,-6]
#integer_list = [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2]
#integer_list = [5,-5,5,-10,5,-5,5]
integer_list = [-1, -1, 1, -1, 2]

largest_summed_consecutive_subArray = largestSummedConsecutiveSubArray(integer_list)

print('For the original integer array of {}'.format(integer_list))

if (largest_summed_consecutive_subArray == [] or largest_summed_consecutive_subArray[0] == []):
largest_summed_consecutive_subArray = []
sum = None
else:
sum = sum(largest_summed_consecutive_subArray[0])

print('The largest summed consecutive sub array: {} with a sum of {}.'.format(largest_summed_consecutive_subArray, sum))```
or at Coding challenge: largest possible sum from consecutive numbers v4, Python 3 - rextester[^]
The sample outputs:
```For the original integer array of []
The largest summed consecutive sub array: [] with a sum of None.

For the original integer array of [-1, -2, -5, -4, -5, -1, -2, -11]
The largest summed consecutive sub array: [] with a sum of None.

For the original integer array of [1, 2, 5, 4, 5, 1, 2, 11]
The largest summed consecutive sub array: [[1, 2, 5, 4, 5, 1, 2, 11]] with a sum of 31.

For the original integer array of [1, 2, -5, 4, 5, -1, 2, -11]
The largest summed consecutive sub array: [[4, 5, -1, 2]] with a sum of 10.

For the original integer array of [5, 5, -3, -6]
The largest summed consecutive sub array: [[5, 5]] with a sum of 10.

For the original integer array of [5, 5, -5, -6]
The largest summed consecutive sub array: [[5, 5]] with a sum of 10.

For the original integer array of [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2]
The largest summed consecutive sub array: [[1, 2, 4], [4, 2, 1], [3, 2, 2]] with a sum of 7.

For the original integer array of [5, -5, 5, -10, 5, -5, 5]
The largest summed consecutive sub array: [[5, -5, 5], [5, -5, 5]] with a sum of 5.

For the original integer array of [-1, -1, 1, -1, 2]
The largest summed consecutive sub array: [[1, -1, 2]] with a sum of 2.```
Fixed a bug!
v14
Bryian Tan 4-Feb-17 21:27pm

What should be the answer for [5,5,-5,-6]?
Peter Leow 4-Feb-17 23:46pm

That breaks the code. Thank you for testing.
Graeme_Grant 5-Feb-17 1:03am

Also try [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2] - there are 3 different possibilities...

Also [5,-5,5,-10,5,-5,5] & [5,-5,5,-5,5] from PIEBALDConsult...

Lastly, should an empty array [] calculate to a value (as pointed out by PIEBALDConsult) or a null value?
Peter Leow 5-Feb-17 1:32am

Just fix it after gotten feedback from Bryian Tan. Thanks you guys for testing it. Code is not elegant but just a quick way to capture the logic. As regards whether null or zero for empty is just a matter of if else IMHO, so up to individual.
Graeme_Grant 5-Feb-17 1:40am

Just tried it and works well. Though, it does not handle more than one possible solution/answer, only the first.
Peter Leow 5-Feb-17 2:16am

I have just incorporated the multiple sub arrays. As for [5, -5, 5, -5, 5], the acceptable sub array is debatable.
Graeme_Grant 5-Feb-17 2:19am

Looks good. :)

Yes, [5, -5, 5, -5, 5] is an interesting one. I think though the sum of the result and the size of the array is all that matters - if it fits within the defined rules, then it is valid.
Peter Leow 5-Feb-17 1:32am

Thanks for the feedback, just fix it. Hope it works now.
Bryian Tan 5-Feb-17 16:45pm

Nice!!! Sorry, I have to throw in another one. [-1, -1, 1, -1, 2] should be 2 right? instead of []
PIEBALDconsult 5-Feb-17 18:59pm

If you seek the _longest_ subarray with the greatest sum, it's [ 1 , -1 , 2 ]
Bryian Tan 5-Feb-17 19:16pm

OK, so the sum should be 2 then. Thanks.
Peter Leow 6-Feb-17 3:02am

Thank you again. That helps me to discover one litter bug:
for i in largest_summed_consecutive_subArray[:]:
Fixed and run well. It seems...
Bryian Tan 6-Feb-17 9:28am

awesome sauce !!!

## Solution 3

Here's my implementation from 2015-07-30, probably late at night, which may not be an excuse.

The output is rather cryptic, but using Peter's example of `[1, 2, -5, 4, 5, -1, 2, -11]` you can see the final output line:

```3   4   4  10  |    1   2  -5  [  4   5  -1   2 ] -11
|       |   |                  ------------------Subarray
|       |   |Sum of subarray
|       |Length of subarray
|Index of subarray
```

```# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>

/**************************************************************************************************************/

typedef struct
{
int        all ; /* Number of data items allocated    */
int        len ; /* Number of data items in use       */

struct     rec   /* Structure to hold one subsequence */
{
int      ind ; /* Index                             */
int      val ; /* Value                             */
int      len ; /* Length                            */
int      sum ; /* Sum                               */
}*         dat ; /* Array of data items               */

struct rec max ; /* Candidate for maximum subsequence */

} ARR ;

# define MAX(x)   ((x)->max)
# define ITM(x,y) ((x)->dat[y])

/**************************************************************************************************************/

ARR*
Init
(
int  n
)
{
ARR* result = (typeof(ARR*)) calloc ( 1 , sizeof(ARR) ) ;

if ( result != NULL )
{
MAX ( result ).sum = INT_MIN ;

result->dat = (typeof(MAX(result))*) calloc ( result->all = n , sizeof(MAX(result)) ) ;
}

return ( result ) ;
}

/**************************************************************************************************************/

void
Disp
(
ARR* a
)
{
if ( a != NULL )
{
if ( a->dat != NULL )
{
free ( a->dat ) ;
}

free ( a ) ;
}

return ;
}

/**************************************************************************************************************/

void
Append
(
ARR*  a
,
char* v
)
{
ITM ( a , a->len ).ind = a->len ;
ITM ( a , a->len ).val = atoi ( v ) ;

(void) printf ( "\n%3d %3d" , ITM ( a , a->len ).ind , ITM ( a , a->len ).val ) ;

a->len++ ;

return ;
}

/**************************************************************************************************************/

void
Show
(
ARR* a
)
{
(void) printf ( "\n       %3d %3d %3d %3d  |  " , MAX(a).ind , MAX(a).val , MAX(a).len , MAX(a).sum ) ;

for ( int i = 0 ; i < a->len ; i++ )
{
if ( i == MAX(a).ind ) printf ( " [" ) ;

(void) printf ( "%3d " , ITM(a,i).val ) ;

if ( i == MAX(a).ind + MAX(a).len - 1 ) printf ( "] " ) ;
}

return ;
}

/**************************************************************************************************************/

void
Process
(
ARR* a
)
{
for ( int i = MAX(a).ind ; i < a->len ; i++ )
{
ITM(a,i).sum += ITM(a,a->len-1).val ;
ITM(a,i).len++ ;

if ( ( MAX(a).sum < ITM(a,i).sum ) || ( ( MAX(a).sum == ITM(a,i).sum ) && ( MAX(a).len < ITM(a,i).len ) ) )
{
(void) memcpy ( &MAX(a) , &ITM(a,i) , sizeof(MAX(a)) ) ;

Show ( a ) ;
}
}

return ;
}

/**************************************************************************************************************/

int
main
(
int   argc
,
char* argv[]
)
{
int result = 0 ;

if ( argc > 1 )
{
ARR* a = Init ( argc - 1 ) ;

if ( ( a != NULL ) && ( a->dat != NULL ) )
{
for ( int i = 0 ; i < a->all ; i++ )
{
Append ( a , argv [ i + 1 ] ) ;

Process ( a ) ;
}

Show ( a ) ;

result = MAX ( a ).len ;
}

Disp ( a ) ;
}

return ( result ) ;
}```

## Solution 5

My solution with Clipper language.
```*
clear
test({})
test({-1, -2, -5, -4, -5, -1, -2, -11})
test({1, 2, 5, 4, 5, 1, 2, 11})
test({1, 2, -5, 4, 5, -1, 2, -11})
test({5, -5, 5, -10, 5, -5, 5})
return

procedure test(lst)
? atos(lst)
tmp= max_tot(lst)
? atos(tmp)
? "Total="
tot= 0
aeval(tmp, {|_1| tot += _1})
?? tot
?
return

function max_tot(lst)
rep={}
if len(lst) != 0
cumul= array(len(lst)+ 1)
cumul[1]= 0
for scan= 1 to len(lst)
cumul[scan+1]= cumul[scan]+ lst[scan]
next
bestd= 1
bestf= 2
bestv= cumul[2]
for scand= 1 to len(cumul)-1
for scanf= scand+1 to len(cumul)
if bestv< cumul[scanf]-cumul[scand]
bestd= scand
bestf= scanf
bestv= cumul[scanf]-cumul[scand]
endif
next
next
for scan= bestd to bestf-1
next
endif
return rep

function atos(lst)
rep="{"
for scan= 1 to len(lst)
if scan != 1
rep += ","
endif
rep += str(lst[scan],,,.T.)
next
rep += "}"
return rep```

What the program does:
- When given not data, the answer is an empty list, sum is 0.
- When given data, the program deals with that data whatever is this data, the answer will be at least 1 value. contrary to Chris Hint, the answer is not an empty list in this case because the statement do not imply it.
- My program answer only the first sequence that gives maximum sum because the statement do not ask for all possible sequences and not sequence of maximum length.
```{}
{}
Total=         0

{-1,-2,-5,-4,-5,-1,-2,-11}
{-1}
Total=        -1

{1,2,5,4,5,1,2,11}
{1,2,5,4,5,1,2,11}
Total=        31

{1,2,-5,4,5,-1,2,-11}
{4,5,-1,2}
Total=        10

{5,-5,5,-10,5,-5,5}
{5}
Total=         5```

Note: I remember seeing this in QA some time ago.
v4
Graeme_Grant 4-Feb-17 20:37pm

"If all are negative then the answer is an empty array.", so {-1} is not a valid result.
Patrice T 4-Feb-17 20:40pm

Read second line in my solution.
Graeme_Grant 4-Feb-17 20:43pm

I did but it does not meet the requirements.
Patrice T 4-Feb-17 20:46pm

I think my way is better.
PIEBALDconsult 4-Feb-17 23:02pm

I agree. Unclear and weird spec.
PIEBALDconsult 4-Feb-17 23:03pm

I think that part of the spec is total BS.
Graeme_Grant 4-Feb-17 23:09pm

I did not write it... I just made sure that I met it regardless of what I thought of it.  no bonus points for attitude... ;)
Graeme_Grant 4-Feb-17 21:10pm

For {5,-5,5,-10,5,-5,5}, the largest group is {5,-5,5} with a sum of 5
PIEBALDconsult 5-Feb-17 1:11am

But there are two congruent yet distinct solutions.
Graeme_Grant 5-Feb-17 1:18am

Yes, and if you look at the output from my solution I list them both. :)

## Solution 6

A variant solution which conform to negative list special case as stated.
```*
clear
test({})
test({-1, -2, -5, -4, -5, -1, -2, -11})
test({1, 2, 5, 4, 5, 1, 2, 11})
test({1, 2, -5, 4, 5, -1, 2, -11})
test({5, -5, 5, -10, 5, -5, 5})
return

procedure test(lst)
? atos(lst)
tmp= max_tot(lst)
? atos(tmp)
? "Total="
tot= 0
aeval(tmp, {|_1| tot += _1})
?? tot
?
return

function max_tot(lst)
rep={}
if len(lst) != 0
cumul= array(len(lst)+ 1)
cumul[1]= 0
for scan= 1 to len(lst)
cumul[scan+1]= cumul[scan]+ lst[scan]
next
bestd= 1
bestf= 2
bestv= cumul[2]
for scand= 1 to len(cumul)-1
for scanf= scand+1 to len(cumul)
if bestv< cumul[scanf]-cumul[scand]
bestd= scand
bestf= scanf
bestv= cumul[scanf]-cumul[scand]
endif
next
next
if bestv > 0
for scan= bestd to bestf-1
next
endif
endif
return rep

function atos(lst)
rep="{"
for scan= 1 to len(lst)
if scan != 1
rep += ","
endif
rep += str(lst[scan],,,.T.)
next
rep += "}"
return rep```

```{}
{}
Total=         0

{-1,-2,-5,-4,-5,-1,-2,-11}
{}
Total=        0

{1,2,5,4,5,1,2,11}
{1,2,5,4,5,1,2,11}
Total=        31

{1,2,-5,4,5,-1,2,-11}
{4,5,-1,2}
Total=        10

{5,-5,5,-10,5,-5,5}
{5}
Total=         5```
v2
Graeme_Grant 5-Feb-17 17:24pm

You need to check the last test... For {5,-5,5,-10,5,-5,5}, the largest group is {5,-5,5} with a sum of 5
Patrice T 5-Feb-17 19:22pm

Yes, but not stated like that.
requirement is sequence with largest sum, not largest sequence with largest sum.
Graeme_Grant 5-Feb-17 19:32pm

There are multiple sequences with the same sum of 5 - 4 x [5]s and 2 x [5,-5,5]. Why is the shortest array the correct one and which of the 4? The obvious answer is the longest arrays.

But here is another with 3 different results with the same sum, which is correct? [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2] - the answer, I feel, is they are all equally correct.
Patrice T 5-Feb-17 19:43pm

"The obvious answer is the longest arrays."
I don't say that a sequence is better than another.
I just list the first one that satisfy the requirement.
Graeme_Grant 5-Feb-17 19:45pm

"find the set of consecutive numbers" implies the longest set.
Patrice T 5-Feb-17 19:49pm

we don't speak same English.
Graeme_Grant 5-Feb-17 19:51pm

okay
PIEBALDconsult 5-Feb-17 20:17pm

Word.

## Solution 7

Here's another take on the problem.

```public sealed class SubArray
{
public int Index  { get ; private set ; }
public int Length { get ; private set ; }
public int Sum    { get ; private set ; }

public SubArray
(
int Index
,
int Length
,
int Sum
)
{
this.Index  = Index  ;
this.Length = Length ;
this.Sum    = Sum    ;

return ;
}

public static System.Collections.Generic.IList<SubArray>
GetMax
(
System.Collections.Generic.IList<int> Value
)
{
System.Collections.Generic.List<SubArray> result =
new System.Collections.Generic.List<SubArray>() ;

if ( ( Value != null ) && ( Value.Count > 0 ) )
{
int[,] work = new int [ Value.Count , Value.Count ] ;

int max = System.Int32.MinValue ;

for ( int i = 0 ; i < Value.Count ; i++ )
{
for ( int j = 0 ; j <= i ; j++ )
{
work [ j , i - j ] = Value [ i ] + ( ( i - j > 0 ) ? work [ j , i - j - 1 ] : 0 ) ;

if  ( max < work [ j , i - j ] )
{
max = work [ j , i - j ] ;
}
}
}

for ( int i = 0 ; i < Value.Count ; i++ )
{
for ( int j = 0 ; j <= i ; j++ )
{
if  ( max == work [ j , i - j ] )
{
result.Add ( new SubArray ( j , i - j + 1  , work [ j , i - j ] ) ) ;
}
}
}
}

}
}```

## Solution 8

Here is a version done in Free Pascal. A little more verbose than C#...

Update: Added equivilent vanilla (no Linq used) C# & VB.Net conversions as a comparison.

```Program LargestGroupSum(output);

type
r = record
d: array of integer;
l, s: integer;
end;
rr = array of r;

function FormatArray(a: array of integer) : string;
var
i: integer;
s, t: string;

begin
s := '[ ';
for i := Low(a) to High(a) do
begin
Str(a[i], t);
s := s + t + ' ';
end;
FormatArray := s + '] ';
end;

procedure DisplayResult(o: array of integer; a: rr);
var
i: integer;
s: string;

begin
s := 'For ' + FormatArray(o) + 'there ';
if (High(a) = -1) then
s := s + 'are no sets'
else if (High(a) > 0) then
s := s + 'are multiple sets'
else
s := s + 'is one set';
writeln(s);
for i := Low(a) to High(a) do
begin
writeln('... the largest group is ', FormatArray(a[i].d),
'with a sum of ', a[i].s);
end;
writeln('');
end;

function Process(a: array of integer) : rr;
var
g: rr = Nil;
res: rr = Nil;
i, j, k, c, d: integer;
m: integer = 0;
n: integer = 0;
o: integer = 0;
p: integer = 0;

begin
c := High(a) + 1;
SetLength(g, Trunc(c * (c + 1) / 2));
for i:= Low(a) to c do
begin
for j := i to c - 1 do
begin
d := 0;
for k := i to j do
begin
SetLength(g[p].d, d + 1);
g[p].d[d] := a[k];
g[p].s := g[p].s + a[k];
d := d + 1;
end;
g[p].l := High(g[p].d) + 1;
if (g[p].s > m) then
begin
o := 1;
m := g[p].s;
n := g[p].l;
end
else if (g[p].s = m) and (g[p].l >= n) then
begin
if g[p].l > n then
begin
o := 1;
n := g[p].l;
end
else
o := o + 1;
end;
p := p + 1;
end;
end;
j := 0;
SetLength(res, o);
for i:= Low(g) to High(g) do
begin
if (g[i].s = m) and (g[i].l = n) then
begin
res[j].d := Copy(g[i].d, Low(g[i].d), High(g[i].d) + 1);
res[j].s := g[i].s;
res[j].l := g[i].l;
j := j + 1;
end;
end;
Process := res;
end;

function LargestGroupSumList(a: array of integer) : rr;
var
res: rr = Nil;
i, c: integer;
nc: integer = 0;
zc: integer = 0;

begin
c := High(a);
if c = 0 then
Exit(res)
else
begin
for i := Low(a) to c do
begin
if (a[i] = 0) then
zc := zc + 1
else if (a[i] < 0) then
nc := nc + 1
end;
if (zc = c) or (nc = c) then
Exit(res);
LargestGroupSumList := Process(a);
end;
end;

var
t1: array of integer = Nil;
t2: array[1..8] of integer = (-1, -2, -5, -4, -5, -1, -2, -11);
t3: array[1..8] of integer = (1, 2, 5, 4, 5, 1, 2, 11);
t4: array[1..8] of integer = (1, 2, -5, 4, 5, -1, 2, -11);
t5: array[1..11] of integer = (1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2);
t6: array[1..7] of integer = (5, -5, 5, -10, 5, -5, 5);
t7: array[1..5] of integer = (5, -5, 5, -5, 5);
t8: array[1..4] of integer = (5, 5, -5, -6);

begin
writeln('Largest possible sum of consecutive numbers');
writeln('===========================================');
writeln('');
DisplayResult(t1, LargestGroupSumList(t1));
DisplayResult(t2, LargestGroupSumList(t2));
DisplayResult(t3, LargestGroupSumList(t3));
DisplayResult(t4, LargestGroupSumList(t4));
DisplayResult(t5, LargestGroupSumList(t5));
DisplayResult(t6, LargestGroupSumList(t6));
DisplayResult(t7, LargestGroupSumList(t7));
DisplayResult(t8, LargestGroupSumList(t8));
end.```

```using System;

namespace LargestGroupSum
{
static class Program
{
static void Main(string[] args)
{
var t1 = new int[] { };
var t2 = new int[] { -1, -2, -5, -4, -5, -1, -2, -11 };
var t3 = new int[] { 1, 2, 5, 4, 5, 1, 2, 11 };
var t4 = new int[] { 1, 2, -5, 4, 5, -1, 2, -11 };
var t5 = new int[] { 1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2 };
var t6 = new int[] { 5, -5, 5, -10, 5, -5, 5 };
var t7 = new int[] { 5, -5, 5, -5, 5 };
var t8 = new int[] { 5, 5, -5, -6 };

Console.WriteLine("Largest possible sum of consecutive numbers");
Console.WriteLine("===========================================\r\n");
DisplayResult(t1, LargestGroupSumList(t1));
DisplayResult(t2, LargestGroupSumList(t2));
DisplayResult(t3, LargestGroupSumList(t3));
DisplayResult(t4, LargestGroupSumList(t4));
DisplayResult(t5, LargestGroupSumList(t5));
DisplayResult(t6, LargestGroupSumList(t6));
DisplayResult(t7, LargestGroupSumList(t7));
DisplayResult(t8, LargestGroupSumList(t8));
Console.WriteLine("\r\n-- Press any key to exit --");
}

static string FormatArray(int[] a)
=> \$"[ {string.Join(", ", a)} ] ";

static void DisplayResult(int[] o, r[] a)
{
Console.WriteLine(\$"For {FormatArray(o)}there {(a.Length > 1 ? "are multiple sets" : a.Length == 0 ? "are no sets" : "is one set")}");
for (int i = 0; i < a.Length; i++)
if (a[i].d != null) Console.WriteLine(\$"... the largest group is {FormatArray(a[i].d)}with a sum of {a[i].s}");
Console.WriteLine();
}

static r[] Process(int[] a)
{
int c = a.Length, d, m, n, o, p = m = n = o = 0;
r[] res;
var g = new r[c * (c + 1) / 2];
for (int i = 0; i < c; i++)
for (int j = i; j < c; j++)
{
d = 0;
g[p] = new r();
g[p].d = new int[Math.Abs(i - j) + 1];
for (int k = i; k <= j; k++)
{
g[p].d[d++] = a[k];
g[p].s += a[k];
}
g[p].l = g[p].d.Length;
if (g[p].s > m)
{
o = 1;
m = g[p].s;
n = g[p].l;
}
else if (g[p].s == m && g[p].l >= n)
{
if (g[p].l > n)
{
o = 1;
n = g[p].l;
}
else
o++;
}
p++;
}
int x = 0;
res = new r[o];
for (int i = 0; i < g.Length; i++)
if (g[i].s == m && g[i].l == n)
res[x++] = g[i];
return res;
}

static r[] LargestGroupSumList(int[] a)
{
int nc, zc = nc = 0, c = a.Length;
if (a.Length == 0) return new r[] { };
for (int i = 0; i < a.Length; i++)
if (a[i] == 0) zc++;
else if (a[i] < 0) nc++;
if (zc == c || nc == c) return new r[] { };
return Process(a);
}
}

class r
{
public int l { get; set; }
public int s { get; set; }
public int[] d { get; set; }
}
}```

```Module Module1

Sub Main(args As String())
Dim t1 = New Integer() {}
Dim t2 = New Integer() {-1, -2, -5, -4, -5, -1, -2, -11}
Dim t3 = New Integer() {1, 2, 5, 4, 5, 1, 2, 11}
Dim t4 = New Integer() {1, 2, -5, 4, 5, -1, 2, -11}
Dim t5 = New Integer() {1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2}
Dim t6 = New Integer() {5, -5, 5, -10, 5, -5, 5}
Dim t7 = New Integer() {5, -5, 5, -5, 5}
Dim t8 = New Integer() {5, 5, -5, -6}

Console.WriteLine("Largest possible sum of consecutive numbers")
Console.WriteLine("===========================================" & vbCrLf)
DisplayResult(t1, LargestGroupSumList(t1))
DisplayResult(t2, LargestGroupSumList(t2))
DisplayResult(t3, LargestGroupSumList(t3))
DisplayResult(t4, LargestGroupSumList(t4))
DisplayResult(t5, LargestGroupSumList(t5))
DisplayResult(t6, LargestGroupSumList(t6))
DisplayResult(t7, LargestGroupSumList(t7))
DisplayResult(t8, LargestGroupSumList(t8))
Console.WriteLine(vbCrLf & "-- Press any key to exit --")
End Sub

Function FormatArray(a As Integer()) As String
Return String.Format("[ {0} ] ", String.Join(", ", a))
End Function

Sub DisplayResult(o As Integer(), a As r())
Console.WriteLine("For {0}there {1}", FormatArray(o), If(a.Length > 1, "are multiple sets", If(a.Length = 0, "are no sets", "is one set")))
For i As Integer = 0 To a.Length - 1
If a(i).d IsNot Nothing Then
Console.WriteLine("... the largest group is {0}with a sum of {1}", FormatArray(a(i).d), a(i).s)
End If
Next
Console.WriteLine()
End Sub

Function Process(a As Integer()) As r()

Dim c As Integer = a.Length, d As Integer
Dim m As Integer = 0, n As Integer = 0, o As Integer = 0, p As Integer = 0
Dim res As r()
Dim g = New r(c * (c + 1) / 2 - 1) {}
For i As Integer = 0 To c - 1
For j As Integer = i To c - 1
d = 0
g(p) = New r()
g(p).d = New Integer(Math.Abs(i - j)) {}
For k As Integer = i To j
g(p).d(d) = a(k)
g(p).s += a(k)
d += 1
Next
g(p).l = g(p).d.Length
If g(p).s > m Then
o = 1
m = g(p).s
n = g(p).l
ElseIf g(p).s = m AndAlso g(p).l >= n Then
If g(p).l > n Then
o = 1
n = g(p).l
Else
o += 1
End If
End If
p += 1
Next
Next
Dim x As Integer = 0
res = New r(o - 1) {}
For i As Integer = 0 To g.Length - 1
If g(i).s = m AndAlso g(i).l = n Then
res(x) = g(i)
x += 1
End If
Next
Return res
End Function

Function LargestGroupSumList(a As Integer()) As r()

Dim nc As Integer, zc As Integer = nc = 0, c As Integer = a.Length
If a.Length = 0 Then Return New r() {}
For i As Integer = 0 To a.Length - 1
If a(i) = 0 Then
zc += 1
ElseIf a(i) < 0 Then
nc += 1
End If
Next
If zc = c OrElse nc = c Then Return New r() {}
Return Process(a)

End Function

End Module

Class r
Public Property l As Integer
Public Property s As Integer
Public Property d As Integer()
End Class```

Here is the output (Free Pascal version, but C# & VB.Net are the same):
```sh-4.3\$ fpc -vw main.pas
Free Pascal Compiler version 2.6.4 [2015/06/17] for x86_64
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling main.pas

/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
157 lines compiled, 0.1 sec
sh-4.3\$ main

Largest possible sum of consecutive numbers
===========================================

For [ ] there are no sets

For [ -1 -2 -5 -4 -5 -1 -2 -11 ] there are no sets

For [ 1 2 5 4 5 1 2 11 ] there is one set
... the largest group is [ 1 2 5 4 5 1 2 11 ] with a sum of 31

For [ 1 2 -5 4 5 -1 2 -11 ] there is one set
... the largest group is [ 4 5 -1 2 ] with a sum of 10

For [ 1 2 4 -20 4 2 1 -15 3 2 2 ] there are multiple sets
... the largest group is [ 1 2 4 ] with a sum of 7
... the largest group is [ 4 2 1 ] with a sum of 7
... the largest group is [ 3 2 2 ] with a sum of 7

For [ 5 -5 5 -10 5 -5 5 ] there are multiple sets
... the largest group is [ 5 -5 5 ] with a sum of 5
... the largest group is [ 5 -5 5 ] with a sum of 5

For [ 5 -5 5 -5 5 ] there is one set
... the largest group is [ 5 -5 5 -5 5 ] with a sum of 5

For [ 5 5 -5 -6 ] there is one set
... the largest group is [ 5 5 ] with a sum of 10

sh-4.3\$```

You can try the Free Pascal version online[^], C# version[^], or VB.Net version[^].
v3
Graeme_Grant 7-Feb-17 9:43am

The online link in solution appears to have a problem. here is a new link[^] where you can run it. - solution now has the revised host link.

## Solution 9

I like compact code and I hate PHP...
```function largest_sum(\$list) {
\$new = array();
\$sub = array();

array_push(\$list, 0);

foreach (\$list as \$key => \$value) {
if(\$value <= 0) {
\$sum = array_sum(\$sub);
\$next = array_key_exists(\$key + 1, \$list) ? \$list[\$key + 1] : false;

if((\$next) && (\$next > \$value) && (abs(\$value) < \$sum)) {
array_push(\$sub, \$value);
continue;
}

\$new[\$sum] = \$sub;
\$sub = array();
}
else {
array_push(\$sub, \$value);
}
}

ksort(\$new);

return(end(\$new));
}```
v2
PIEBALDconsult 6-Feb-17 8:56am

Does that return only the maximum sum? Not the subarray?
Kornfeld Eliyahu Peter 6-Feb-17 9:18am

\$new is an array of arrays... end(\$new) will return the last array after sort...
Graeme_Grant 7-Feb-17 7:18am

I'm not a php programmer, but with the help of Google, I just ran tests on RexTester[^] with this and it requires more work.

* (-1,-2,-5,-4,-5,-1,-2,-11) returned [] - correct
* (1,2,5,4,5,1,2,11) returned [1,2,5,4,5,1,2,11] - correct
* (1,2,-5,4,5,-1,2,-11) returned [4,5] sum: 9 - not [4,5,-1,2] sum: 10
* (1,2,4,-20,4,2,1,-15,3,2,2) returned [3,2,2] - last of 3, also [1,2,4] & [4,2,1]
* (5,-5,5,-10,5,-5,5) returned [5] - not [5, -5, 5]
* (5,-5,5,-5,5) returned [5] - not [5, -5, 5, -5, 5]
* (5,5,-5,-6) returned [5,5] - correct
* (-1,-1,1,-1,2) returned [2] - not [1, -1, 2]
Kornfeld Eliyahu Peter 7-Feb-17 7:38am

This is not a PHP problem, the algorithm isn't perfect (or in other words - the problem is me :-))...
However...
* (1,2,4,-20,4,2,1,-15,3,2,2) returned [3,2,2] - last of 3, also [1,2,4] & [4,2,1] - It is all right, there is no requirement to return all, or first... As I use the sum as index it will always return the last group...

* (5,-5,5,-10,5,-5,5) returned [5] - not [5, -5, 5]
* (5,-5,5,-5,5) returned [5] - not [5, -5, 5, -5, 5]
* (-1,-1,1,-1,2) returned [2] - not [1, -1, 2] - All these are irrelevant cases. The question is about the largest sum and not about the longest array...

* (1,2,-5,4,5,-1,2,-11) returned [4,5] sum: 9 - not [4,5,-1,2] sum: 10 - This one is the only error... I will see what can I do... But I hate PHP :-)

I would upvote your effort here, but can not :thumbs:!!!
Kornfeld Eliyahu Peter 7-Feb-17 9:16am

Check updated version... If you wish :-)
Graeme_Grant 7-Feb-17 9:32am

I tried the new version[^] and works better. :)

Top Experts
Last 24hrsThis month
 OriginalGriff 233 Maciej Los 100 MadMyche 90 CHill60 70 CPallini 70
 OriginalGriff 3,939 Maciej Los 1,825 RickZeeland 1,560 Richard MacCutchan 1,443 Wendelius 1,000