Click here to Skip to main content
13,194,242 members (48,163 online)
Rate this:
 
Please Sign up or sign in to vote.
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 3-Feb-17 5:31am
Updated 6-Feb-17 1:06am
Comments
ppolymorphe 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...
ppolymorphe 4-Feb-17 20:24pm
   
didn't it ask for an answer ?
Does it ask for all answers ?
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
ppolymorphe 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... ;)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 4

Update 3: Added VB.Net versions

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 --");
            Console.ReadKey();
        }
    }
 
    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++)
                        groups.Add(list.Skip(i).Take(j + 1).ToList());
                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)
        Console.ReadKey()
    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
                    groups.Add(list.Skip(i).Take(j + 1).ToList())
                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 --");
            Console.ReadKey();
        }
    }
 
    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++)
                        groups.Add(list.Skip(i).Take(j + 1).ToList());
 
                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)
        Console.ReadKey()
    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
                    groups.Add(list.Skip(i).Take(j + 1).ToList())
                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()
  Permalink  
v24
Comments
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! :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

I'd use Kadane's algorithm[^]:
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;
    }
  Permalink  
Comments
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[^]
Rate this: bad
 
good
Please Sign up or sign in to vote.

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!
  Permalink  
v14
Comments
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 !!!
Rate this: bad
 
good
Please Sign up or sign in to vote.

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 ) ;
}
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

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
			aadd(rep, lst[scan])
		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.
  Permalink  
v4
Comments
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.
ppolymorphe 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.
ppolymorphe 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. [edit] 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. :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

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
				aadd(rep, lst[scan])
			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
  Permalink  
v2
Comments
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
ppolymorphe 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.
ppolymorphe 5-Feb-17 19:43pm
   
"The obvious answer is the longest arrays."
Your opinion.
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.
ppolymorphe 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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

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 ] ) ) ;
          }
        }
      }
    }
 
    return ( result.AsReadOnly() ) ;
  }
}
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

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 --");
            Console.ReadKey();
        }
 
        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 --")
        Console.ReadKey()
    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
Linking main
 

 

/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[^].
  Permalink  
v3
Comments
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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

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));
}
  Permalink  
v2
Comments
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. :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy |
Web03 | 2.8.171018.2 | Last Updated 10 Feb 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100