给定一个整数数组。找到和最大的最大子数组

Question

你好，我正在为一次面试代码测试做准备，并遇到了这个问题。我尝试用C#来解决它，下面是我丢脸的答案，我甚至不知道它是否正确，但我猜大多数情况下都不正确，能否有人请好心提供答案，这样当我重新制定解决方案时，我至少可以有答案来验证输出。谢谢。

示例数据：

int[] arr = {5, 1, -7, 3, 7};

代码：

int[] LargestsubarrayMaxSum(int[] arr)
{
    int temp = 0;
    int[] resultArr = new int[arr.Length];

    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (i != 0)
        {
            foreach (int item in resultArr)
            {
                temp += item;
            }

            if (temp + arr[i + 1] > 0)
            {
                resultArr[i + 1] = temp + arr[i + 1];
            }
        }
        else
        {
            if ((arr[i] + arr[i + 1]) >= 0)
            {
                resultArr[i] = arr[i];
                resultArr[i + 1] = arr[i] + arr[i + 1];
            }
            else
            {
                resultArr[i] = arr[i];
                resultArr[i + 1] = 0;
            }
        }
    }
    return resultArr;
}

- k80sg

---

这基本上是在说要返回所有正整数吗？最大子数组的大小可以有多大？ - Adam Houldsworth

@Adam - 如果所有值都是正数，我会假设最大的子数组是整个数组。 - Lieven Keersmaekers

@Lieven 恰好是我所想的 :-) - Adam Houldsworth

@Adam 对于这个问题，“子数组”和“子集”不是同一回事 - 子数组由源数组中连续的元素组成。 - AakashM

@AakashM 啊，这就是问题的关键，我知道我没有看到它。谢谢你澄清。 - Adam Houldsworth

我仍然不理解，“具有最大总和的最大子数组”。为什么4 + 5 +（-2）+ 1 = 8比4 + 5 = 9更好。现在，显然，前者有更多的元素..但是你如何决定哪个更好.. - user606723

Answer 1

这个怎么样？

var arr = new [] {5, 1, -7, 3, 7};

var xs =
    from n in Enumerable.Range(0, arr.Length)
    from l in Enumerable.Range(1, arr.Length - n)
    let subseq = arr.Skip(n).Take(l)
    orderby subseq.Count() descending
    orderby subseq.Sum() descending
    select subseq;

var maxSumSubseq = xs.First();

编辑：添加orderby subseq.Count() descending以获取最大长度的子序列。

---

编辑：根据评论添加解释。

1. Select all possible subsequence starting indices:

   from n in Enumerable.Range(0, arr.Length)
   

2. Select all possible lengths of subsequences given the starting index:

   from l in Enumerable.Range(1, arr.Length - n)
   

3. Extract the subsequence from the array:

   let subseq = arr.Skip(n).Take(l)
   

4. Order subsequences by descending length (i.e. longest first) - could order by l instead of subseq.Count() but the latter is more expressive even though the former is more efficient:

   orderby subseq.Count() descending
   

5. Calculate the sum of each subsequence and order the subsequences so highest valued sums are first:

   orderby subseq.Sum() descending
   

6. Select the subsequences:

   select subseq;
   

7. Only select the first subsequence - it's the highest value sum with the greatest length:

   xs.First();
   

希望这可以帮到你。

- Enigmativity

---

无法保证此结果能为 var arr = new [] {5,1,-7,2,2,2} 给出正确答案。 - Bob Vale

对于我尝试过的所有变化，它都返回了正确的结果，但你可能需要解释一下。我不知道这是如何工作的。 - Lieven Keersmaekers

@Lieven - 我添加了每行代码的解释。如果有帮助，请告诉我。谢谢。 - Enigmativity

Answer 2

O(N)时间复杂度和O(1)空间复杂度。这是我所知道的最优解决方案:

#include <stdio.h>
#include <limits.h>

int get_max_sum(int* array, int len, int* start, int* end)
{
    int max_sum = INT_MIN, sum = 0, i;
    int tmp_start = 0;

    for(i = 0; i != len; ++i)
    {
        sum += array[i];

        // if the sum is equal, choose the one with more elements
        if(sum > max_sum || (sum == max_sum && (end - start) < (i - tmp_start)))
        {
            max_sum = sum;
            *start = tmp_start;
            *end = i;
        }
        if(sum < 0)
        {
            sum = 0;
            tmp_start = i + 1;
        }
    }

    return max_sum;
}

以下是一些测试案例：

int main(int argc, char **argv)
{
    int arr1[] = {5, 1, -7, 3, 7};
    int arr2[] = {1};
    int arr3[] = {-1, -7, -3, -7};
    int arr4[] = {5, 1, -7, 2, 2, 2};
    int start, end, sum;

    sum = get_max_sum(arr1, 5, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr2, 1, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr3, 4, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    sum = get_max_sum(arr4, 6, &start, &end);
    printf("sum: %d, start: %d, end: %d\n", sum, start, end);

    return 0;
}

$ ./a.out
sum: 10, start: 3, end: 4
sum: 1, start: 0, end: 0
sum: -1, start: 0, end: 0
sum: 6, start: 3, end: 5

更新1：添加代码以打印子数组的索引。

更新2：如果找到两个和相同的子数组，则选择具有更多元素的子数组。

更新3：修复了针对前导负数的算法。

- Mu Qiao

---

但是您并没有提供最大的子数组，它只给出了总和。 - RG-3

@Mu Qiao - 由于 OP 需要 最大 的子数组，测试用例 #4 应该返回 sum: 6, start: 3, end: 5。 - Lieven Keersmaekers

@Lieven "start: 0, end: 1" 也是最大的子数组。我知道有两个最大的子数组，但我只返回第一个。要找到所有的子数组需要更多的代码，这会让理解变得困难。 - Mu Qiao

@Lieven 现在我明白了并且已经修复了。谢谢。 - Mu Qiao

我必须指出，它仅查找具有最大正数和的子数组。 - expert

Answer 3

你可以使用 Enigmativity 的答案，但要添加额外的排序条件 subseq.Count() descending。

或者，如果你想要一个疯狂的 LINQ 查询……

int[] arr = .......

var result = new[]{0}
             .Concat(arr.Select((x,i)=>new {x,i})
             .Where(a=>a.x<0).Select(a=>a.i+1))
             .Select (i => arr.Skip(i).TakeWhile(a => a>=0))
             .OrderByDescending(a=>a.Sum())
             .OrderByDescending(a=>a.Count()).First();

然而通常情况下，您希望将这些操作作为一个循环来执行。

var result=new List<int>();
var maxResult=new List<int>();

// These next four variables could be calculated on the fly 
// but this way prevents reiterating the list each loop.
var count=0; 
var sum=0;
var maxCount=0;
var maxSum=0;

foreach (var value in arr) {
  if (value >=0) {
    result.Add(value);
    sum+=value;
    count++;
  } else {
    if (sum>maxSum || (sum==maxSum && count>maxCount)) {
      maxSum=sum;
      maxCount=count;
      maxResult=result;
    }
    result.Clear();
    count=0;
    sum=0;
  }
}

var returnValue=maxResult.ToArray();

- Bob Vale

Answer 4

这是一个完全可用的解决方案：

using System;
using System.Collections.Generic;

class MaxSumOfSubArray
{
    static void Main()
    {
        //int[] array = { 2, 3, -6, -1, 2, -1, 6, 4, -8, 8 };
        //maxSubSum(array);

        int digits;
        List<int> array = new List<int>();
        Console.WriteLine("Please enter array of integer values. To exit, enter eny key different than 0..9");

        while (int.TryParse(Console.ReadLine(), out digits))
        {
            array.Add(digits);
        }

        maxSubSum(array);
    }

    public static void maxSubSum(List<int> arr)
    {
        int maxSum = 0;
        int currentSum = 0;
        int i = 0;
        int j = 0;
        int seqStart=0;
        int seqEnd=0;
        while (j < arr.Count)
        {
            currentSum = currentSum + arr[j];

            if (currentSum > maxSum)
            {
                maxSum = currentSum;
                seqStart = i;
                seqEnd = j;
            }
            else if (currentSum < 0)
            {
                i = j + 1;
                currentSum = 0;
            }
            j++;
        }
        Console.Write("The sequence of maximal sum in given array is: {");
        for (int seq = seqStart; seq <= seqEnd; seq++)
        {
            Console.Write(arr[seq] + " ");
        }
        Console.WriteLine("\b}");
        Console.WriteLine("The maximum sum of subarray is: {0}", maxSum);
    }
}

- Deko

Answer 5

    public static int[] FindMaxArrayEx(int[] srcArray)
    {
        int[] maxArray = new int[1];
        int maxTotal = int.MinValue;
        int curIndex = 0;
        int tmpTotal = 0;
        List<int> tmpArray = new List<int>();

        if (srcArray.Length != 1)
        {
            for (int i = 0; i < srcArray.Length; i++)
            {
                tmpTotal = 0;
                curIndex = i;
                tmpArray.Clear();

                while (curIndex < srcArray.Length)
                {
                    tmpTotal += srcArray[curIndex];
                    tmpArray.Add(srcArray[curIndex]);

                    if (tmpTotal > maxTotal)
                    {
                        maxTotal = tmpTotal;
                        maxArray = tmpArray.ToArray();
                    }

                    curIndex++;
                }
            }
        }
        else
        {
            maxTotal = srcArray[0];
            maxArray = srcArray;
        }

        Console.WriteLine("FindMaxArrayEx: {0}",maxTotal);

        return maxArray;

    }

- Tyranticus

---

介意解释一下吗？ - Austin Henley

Answer 6

    /// <summary>
    /// given an non-empty input array of integers, this method returns the largest contiguous sum
    /// </summary>
    /// <param name="inputArray">the non-empty input array of integeres</param>
    /// <returns>int, the largest contiguous sum</returns>
    /// <remarks>time complexity O(n)</remarks>

    static int GetLargestContiguousSum(int[] inputArray)
    {
        //find length of the string, if empty throw an exception            
        if (inputArray.Length == 0)
            throw new ArgumentException("the input parameter cannot be an empty array");

        int maxSum = 0;
        int currentSum = 0;

        maxSum = currentSum = inputArray[0];
        for (int i = 1; i < inputArray.Length; i++) //skip i=0 as currentSum=inputArray[0].
        {
            currentSum = Math.Max(currentSum + inputArray[i], inputArray[i]);
            maxSum = Math.Max(currentSum, maxSum);
        }
        return maxSum;
    }

- Som Poddar

Answer 7

/*--这是我在维基上找到的计算总和的算法，但要获取实际的子数组， * 我真的必须好好思考。经过几个小时的努力，我使用startIndex和endIndex int变量解决了它， * 然后通过添加一个if语句来判断 if (max_ending_here == array[i]) { startIndex = i; } * 这真的很难。我希望你们都能根据需要进行重构以进行改进。*/

/*  Initialize:
            max_so_far = 0
            max_ending_here = 0

        Loop for each element of the array
            (a) max_ending_here = max_ending_here + a[i]
            (b) if(max_ending_here < 0)
                    max_ending_here = 0
            (c) if(max_so_far < max_ending_here)
                    max_so_far = max_ending_here
        return max_so_far*/

        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        namespace ConsoleApplication3
        {
            class Program
            {
                static void Main(string[] args)
                {
                    int[] array = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
                    int[] largestSubArray;
                    largestSubArray = Max_Array(array);
                    Console.WriteLine();

                    Console.WriteLine("Subarray is :");
                    foreach (int numb in largestSubArray)
                        Console.WriteLine(numb);
                    Console.ReadKey();
                }

                //Max_Array function will calculate the largest contigent array
                //sum and then find out startIndex and endIndex of sub array
                //within for loop.Using this startIndex and endIndex new subarray
                //is created with the name of largestSubArray and values are copied                           
                //from original array. 

                public static int[] Max_Array(int[] array)
                {
                    int[] largestSubArray;
                    int max_so_far = 0, max_ending_here = 0, startIndex = 0,
                        endIndex = 0;

                    for (int i = 0, j = 0; i < array.Length; i++)
                    {
                        max_ending_here += array[i];

                        if (max_ending_here <= 0)
                        {
                            max_ending_here = 0;
                        }

                        if (max_ending_here == array[i])
                            { startIndex = i; }

                        if (max_so_far < max_ending_here)
                        {                                
                            max_so_far = max_ending_here;
                            endIndex = i;
                        }
                    }
                    Console.WriteLine("Largest sum is: {0}", max_so_far);

                    largestSubArray = new int[(endIndex - startIndex) + 1];
                    Array.Copy(array, startIndex, largestSubArray, 0, (endIndex - startIndex) + 1);
                    return largestSubArray;

                }
            }
        }

Output

Largest sum is: 6

'Subarray is:
4,
-1,
2,
1'

- Adnan Bhatti

---

此算法在输入为-1、-2、-3或1、-2、3、4、-10、6等情况下失败。 - Ignacio Soler Garcia

Answer 8

一旦你理解了它，它并不那么复杂。一开始我是反着想的，这对某些原因很有帮助。

1. 如果所有数字都是正数（或0），那么整个数组就是具有最大和的子数组。
2. 现在，我们可以将这个事实应用于正数或负数的数组，而是说我们想要包括所有正数（或0）的子数组。
3. 从结尾开始向左求和。当你找到一个负数时，你会想，“ 这个负数是否使得我的其余总和毫无价值？” 如果没有，你会继续前进...但你也会将该点标记为当前最大和（如果它大于上一个当前最大和）。
4. 如果它们毫无价值（即总和现在小于0），那么你知道你索引右侧的所有内容现在都毫无价值。你仍然保留你的当前最大和，以防它是最高的。
5. 从新的索引3开始。跟踪您当前的最大和和结束的索引。

- user606723

Answer 9

在一个数组中，具有最大和的子数组是没有最小元素的数组。因此，对它进行排序并移除最小元素即可。

如果这个数组仅包含正整数，则该方法适用。否则，只需计算正数元素的子数组即可得到答案。

- Neel Basu

Answer 10

以下代码对我有效：

static void Main(string[] args)
        {
            string str = Console.ReadLine();
            int [] arr = Array.ConvertAll(str.Split(' '),int.Parse);
            int curSum = 0, maxSum = 0;
            curSum = maxSum = arr[0];
            for (int i = 1; i < arr.Length; i++)
            {
                curSum = Math.Max(curSum + arr[i], arr[i]);
                maxSum = Math.Max(curSum, maxSum);
            }
            Console.WriteLine("{0}", maxSum);
            Console.ReadKey();
        }

输入：-2 1 -3 4 -1 2 1 -5 4

输出：6

- Jaydeep Shil