Chris Maunder Ответов: 9

Задача кодирования: максимально возможная сумма из последовательных чисел

Учитывая массив целых чисел-некоторые положительные, некоторые отрицательные, некоторые ни те, ни другие, найдите набор последовательных чисел в этом массиве с максимально возможной суммой.

Очевидно, что если все числа положительны, то ответом будет начальный массив. Если все отрицательные, то ответ-пустой массив. Промежуточный случай-самый интересный.

Patrice T

"найдите в этом массиве множество последовательных чисел с максимально возможной суммой."
Я думаю, что это не означает, что результат должен быть положительным.

PIEBALDconsult

Я согласен. Может быть, он имел в виду"положительный"?

PIEBALDconsult

Пффф. Массивы-это ооочень последнее тысячелетие.
И все же это звучит знакомо. Как будто его здесь уже спрашивали...

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

Graeme_Grant

Что случилось с вызовом на прошлой неделе? Я удивлен, что никто, кроме меня, не попытался это сделать, и победитель не был объявлен.

PIEBALDconsult

Я так и сделал, но на C#. Думаю, я все равно смогу его опубликовать.
Сделано.

Graeme_Grant

Да, мой прототип C# было легко сделать, и, возможно, именно поэтому он не был разрешен.

PIEBALDconsult

Возможно.

PIEBALDconsult

Каким должен быть результат
5 -5 5 -10 5 -5 5
?

Или даже:
5 -5 5 -5 5
?

Graeme_Grant

[5] было бы ответом для обоих

PIEBALDconsult

Нет, он просит массив, а не сумму.

Graeme_Grant

да, скобки представляют собой массив с одним элементом, никакие скобки не будут суммой. ;)

PIEBALDconsult

Но там есть еще подмассивы, сумма которых равна 5.

Graeme_Grant

то есть вы хотите сказать, что ответом должен быть массив массивов, соответствующих критериям? Я действительно размышлял над этим...

Patrice T

разве он не требовал ответа ?
Требует ли он всех ответов ?

Graeme_Grant

Он запрашивает сингулярный результат, но я добавил версию, которая может обрабатывать кратные числа, поскольку это возможно.

Graeme_Grant

Для [5, -5, 5, -10, 5, -5, 5], Существует несколько наборов
... самой большой группой является [5] с суммой 5
... самой большой группой является [5, -5, 5] с суммой 5
... самой большой группой является [5] с суммой 5
... самой большой группой является [5] с суммой 5

Для [5, -5, 5, -5, 5], Существует несколько наборов
... самой большой группой является [5] с суммой 5
... самой большой группой является [5, -5, 5] с суммой 5
... самой большой группой является [5] с суммой 5

Patrice T

"Для [5, -5, 5, -5, 5], Существует несколько наборов"
не скучает ли
.. самая большая группа-это [5, -5, 5, -5, 5] с суммой 5
?

Graeme_Grant

Хороший улов! Теперь корректно обрабатывает все случаи для обеих версий. :)

PIEBALDconsult

Прямо вперед. (Вы оба.)
На мой взгляд (хотя и не в моей реализации), может быть несколько результирующих наборов.
Вопрос от 2015-07 годов требовал самого длинного подмассива, но все же может быть несколько подходящих результирующих наборов.

Graeme_Grant

Вот еще один набор для проверки: [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2]

Есть 3 возможных ответа,каждый из которых отличается.

Bryian Tan

Geezzz. Ты, парень, здесь как сумасшедший ученый-математик. В хорошем смысле :)

PIEBALDconsult

Педанты. Это слово-педанты. (Сказал он педантично.)

Graeme_Grant

Дьявол кроется в деталях... ;)

9 Ответов

Рейтинг:
2

Graeme_Grant

Обновление 3: Добавлено глаг.Сетевая версия

Вот еще один быстрый пример:


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


Выходы:
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 --

И вы можете запустить его онлайн[^]

Обновление
Вот еще одна версия, которая обрабатывает несколько возвращаемых наборов, которые в равной степени являются максимально возможной суммой последовательных чисел.


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()

PIEBALDconsult

Я не согласен с пустым массивом, суммирующимся до нуля.

Graeme_Grant

Мы должны возвращать только массив, но показывать значение суммы-это бонус. Вместо этого вы можете использовать этот вывод:

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

Добавлено обновление, которое не имеет суммы для пустых результатов и теперь обрабатывает несколько наборов с максимально возможной суммой.

Bryian Tan

Каким должен быть ответ на [5,5, -5,-6]?

Graeme_Grant 

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

Graeme_Grant

В этом решении есть ссылки выше, где вы можете ввести свои собственные числа и протестировать их. :)

Graeme_Grant

Вместо того чтобы обновлять решение, вот еще один тестовый набор с результатами:

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

еще один вопрос :) {9,-2,8,-1,-6} , почему самая большая группа - это [9,-2,8], хотя это должны быть последовательные числа

Graeme_Grant

Последовательный (один за другим), а не инкрементный.

Bryian Tan

Понял. Спасибо.

Richard Deeming 

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


Сколько раз вы собираетесь повторять этот список? :P

Вы, конечно, можете удалить первый вызов, чтобы Any - если в списке нет элементов, то в списке также не будет элементов больше 1.

Также может быть проще следовать логике, если вы замените !list.Any(condition) с list.All(!condition):
list.All(x => x <= 1) ? ... : list.All(x => x >= 1) ? ... : ...

Это сразу же делает очевидным, что первое условие должно быть list.All(x => x < 1), нет list.All(x => x <= 1).
(Так что ваша версия должна быть: !list.Any(x => x >= 1))


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

Зовущий OrderBy[Descending] отрицает любой предыдущий заказ. Вы должны либо удалить первый OrderByDescending позвоните или измените второй на ThenByDescending если вы хотите отсортировать по двум разным критериям.

Graeme_Grant

Я внес некоторые изменения, которые отражают некоторые из сделанных предложений. Спасибо! :)

Рейтинг:
2

Patrice T

Вариант решения, который соответствует частному случаю отрицательного списка, как указано.

*
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

Graeme_Grant

Вам нужно проверить последний тест... Для {5,-5,5,-10,5,-5,5}, самая большая группа - {5,-5,5} с суммой 5

Patrice T

Да,но не в таком виде.
требование-это последовательность с наибольшей суммой, а не самая большая последовательность с наибольшей суммой.

Graeme_Grant

Существует несколько последовательностей с одинаковой суммой 5-4 x [5]s и 2 x [5,-5,5]. Почему самый короткий массив является правильным и какой из 4? Очевидный ответ - самые длинные массивы.

Но вот еще один с 3 разными результатами с той же суммой, который является правильным? [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2] - я чувствую, что все они одинаково верны.

Patrice T

"Очевидный ответ - самые длинные массивы."
Ваше мнение.
Я не говорю, что одна последовательность лучше другой.
Я просто перечисляю первый из них, который удовлетворяет этому требованию.

Graeme_Grant

"найти набор последовательных чисел" подразумевает самый длинный набор.

Patrice T

мы не говорим на одном английском языке.

Graeme_Grant

окей

PIEBALDconsult

Слово.

Рейтинг:
1

OriginalGriff

Я бы использовал Алгоритм Кадана[^]:

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

Удовлетворяет ли это спецификации " найти набор последовательных чисел ... ответ - Ан ... массив"?

Graeme_Grant

Я запустил код и обнаружил несколько проблем (помимо того, что не возвращал массивы): [] не обрабатывается и выдает ошибку, и большинство тестов терпят неудачу. здесь представлены тесты онлайн[^]

Рейтинг:
1

Peter Leow

Быстрый, чтобы присоединиться к жаре:

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)))

Выход:
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.
Играть в нее онлайн[^].

++ + + + [Раунд 2]+++++
Спасибо Брайан Тан за тестирование и указание на ошибку. Похоже, что предыдущий код прерывается, когда отрицательное целое число включается в качестве последнего элемента в массив потенциальных решений. Таким образом, исправление состоит в том, чтобы удалить это отрицательное целое число, если оно присутствует в качестве последнего элемента в массиве потенциальных решений. Для этого создается функция:
# 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)))

Демонстрация и тестирование на Задача кодирования: максимально возможная сумма из последовательных чисел v2, Python 3 - rextester[^]

+ + + + + [Раунд 3]+++++
Как указал Graeme_Grant, может быть несколько вхождений суб-массивов, удовлетворяющих наибольшей сумме, поэтому я изменил часть кода, чтобы учесть такой сценарий:
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


Результирующий код является
# 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))
или в Задача кодирования: максимально возможная сумма из последовательных чисел v4, Python 3 - rextester[^]
Примерные выходные данные:
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.
Исправлена ошибка!

Bryian Tan

Каким должен быть ответ на [5,5, -5,-6]?

Peter Leow

Это нарушает кодекс. Спасибо за тестирование.

Graeme_Grant

Также попробуйте [1, 2, 4, -20, 4, 2, 1, -15, 3, 2, 2] - есть 3 различных варианта...

Также [5,-5,5,-10,5,-5,5] & [5,-5,5, -5,5] от PIEBALDConsult...

Наконец, должен ли пустой массив [] вычисляться до значения (как указано PIEBALDConsult) или нулевого значения?

Peter Leow

Просто исправьте это после того, как получите обратную связь от Брайана Тана. Спасибо вам, ребята, за то, что вы его проверили. Код-это не элегантный, а просто быстрый способ уловить логику. Что касается того, является ли нуль или ноль для пустого-это просто вопрос, если еще ИМХО, так что до отдельного человека.

Graeme_Grant

Просто попробовал и хорошо работает. Хотя он не обрабатывает более одного возможного решения/ответа, только первый.

Peter Leow

Я только что включил несколько суб-массивов. Что касается [5, -5, 5, -5, 5], приемлемый суб-массив является спорным.

Graeme_Grant

Выглядеть хорошо. :)

Да, [5, -5, 5, -5, 5] это очень интересно. Я думаю, хотя сумма результата и размер массива-это все, что имеет значение - если он вписывается в определенные правила, то он действителен.

Peter Leow

Спасибо за обратную связь, просто исправьте это. Надеюсь, теперь это сработает.

Bryian Tan

Приятно!!! Извините, но я должен добавить еще один. [-1, -1, 1, -1, 2] должно быть 2, верно? вместо []

PIEBALDconsult

Если вы ищете самый длинный подмассив с наибольшей суммой, то это [ 1, -1, 2 ]

Bryian Tan

Хорошо, тогда сумма должна быть равна 2. Спасибо.

Peter Leow

Спасибо еще раз. Это помогает мне обнаружить одну ошибку помета:
для меня в largest_summed_consecutive_subArray[:]:
Исправлено и работает хорошо. Кажется...

Bryian Tan

потрясающий соус !!!

Рейтинг:
1

PIEBALDconsult

Вот моя реализация от 2015-07-30, вероятно, поздно ночью, что, возможно, не является оправданием.

Вывод довольно загадочный, но на примере Питера [1, 2, -5, 4, 5, -1, 2, -11] вы можете увидеть окончательную выходную строку:

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 ) ;
}

Рейтинг:
1

PIEBALDconsult

Вот еще один взгляд на проблему.

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() ) ;
  }
}

Рейтинг:
1

Graeme_Grant

Вот версия, сделанная на свободном Паскале. Немного более многословный, чем C#...

Обновление: Добавлена эквивилентная ваниль (не используется Linq) C# & VB.Net конверсии в качестве сравнения.


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 Intege

Graeme_Grant

Онлайн-ссылка в решении, по-видимому, имеет проблему. вот такой новая ссылка[^] где вы можете запустить его. - решение теперь имеет пересмотренную ссылку хоста.

Рейтинг:
0

Patrice T

Мое решение с помощью языка Clipper.

*
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

Что делает программа:
- Когда даны не данные, ответ-пустой список, сумма равна 0.
- Когда даны данные, программа имеет дело с этими данными, какими бы ни были эти данные, ответ будет не менее 1 значения. вопреки намеку Криса, ответ в данном случае не является пустым списком, потому что утверждение его не подразумевает.
- Моя программа отвечает только на первую последовательность, которая дает максимальную сумму, потому что оператор не запрашивает все возможные последовательности и не последовательность максимальной длины.
{}
{}
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


Примечание: Я помню, что видел это в QA некоторое время назад.

Graeme_Grant

"Если все отрицательны, то ответ-пустой массив", поэтому {-1} не является допустимым результатом.

Patrice T

Прочтите вторую строчку в моем решении.

Graeme_Grant

Я так и сделал, но это не соответствует требованиям.

Patrice T

Я думаю, что мой путь лучше.

PIEBALDconsult

Я согласен. Неясная и странная спецификация.

PIEBALDconsult

Я думаю,что эта часть спецификации-полная чушь.

Graeme_Grant

Я этого не писал... Я просто позаботился о том, чтобы встретить его, независимо от того, что я о нем думаю. [правка] никаких бонусных баллов за отношение... ;)

Graeme_Grant

Для {5,-5,5,-10,5,-5,5}, самая большая группа - {5,-5,5} с суммой 5

PIEBALDconsult

Но есть два конгруэнтных, но различных решения.

Graeme_Grant

Да, и если вы посмотрите на результат моего решения, я перечислю их обоих. :)

Рейтинг:
0

Kornfeld Eliyahu Peter

Мне нравится компактный код, и я ненавижу 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));
}

PIEBALDconsult

Возвращает ли это только максимальную сумму? Не подмассива?

Kornfeld Eliyahu Peter

$new-это массив массивов... end ($new) вернет последний массив после сортировки...

Graeme_Grant

Я не программист php, но с помощью Google я просто запустил тесты на Рекстестер[^] с этим и требуется больше работы.

* (-1,-2,-5,-4,-5,-1,-2,-11) возвращено [] - правильно
* (1,2,5,4,5,1,2,11) возвращено [1,2,5,4,5,1,2,11] - правильно
* (1,2,-5,4,5,-1,2,-11) возвращено [4,5] сумма: 9-не [4,5,-1,2] сумма: 10
* (1,2,4,-20,4,2,1,-15,3,2,2) возвращено [3,2,2] - последнее из 3, также [1,2,4] & [4,2,1]
* (5,-5,5,-10,5,-5,5) возвращено [5] - не [5, -5, 5]
* (5,-5,5,-5,5) возвращено [5] - Нет [5, -5, 5, -5, 5]
* (5,5,-5,-6) возвращено [5,5] - правильно
* (-1,-1,1,-1,2) возвращено [2] - не [1, -1, 2]

Kornfeld Eliyahu Peter

Это не проблема PHP, алгоритм не идеален (или, другими словами-проблема во мне : -))...
Однако...
* (1,2,4,-20,4,2,1,-15,3,2,2) вернулся [3,2,2] - последний из 3, также [1,2,4] &ампер; [4,2,1] - все в порядке, нет никакого требования, чтобы вернуть все, или первый... Поскольку я использую сумму в качестве индекса, она всегда будет возвращать последнюю группу...

* (5,-5,5,-10,5,-5,5) возвращено [5] - не [5, -5, 5]
* (5,-5,5,-5,5) возвращено [5] - Нет [5, -5, 5, -5, 5]
* (-1,-1,1,-1,2) возвращено [2] - не [1, -1, 2] - Все это несущественные случаи. Речь идет о самой большой сумме, а не о самом длинном массиве...

* (1,2,-5,4,5,-1,2,-11) возвращенная [4,5] сумма: 9-не [4,5, -1,2] сумма: 10-это единственная ошибка... Я посмотрю, что можно сделать... Но я ненавижу PHP :-)

Я бы высоко оценил ваши усилия здесь, но не могу :большие пальцы:!!!

Kornfeld Eliyahu Peter

Проверьте обновленную версию... Если хотите :-)

Graeme_Grant

Я попробовал новая версия[^] и работает лучше. :)