c# - 给定一个整数数组。找到具有最大总和的最大子数组

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

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. 选择所有可能的子序列起始索引:

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

2. 给定起始索引选择所有可能长度的子序列:

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

3. 从数组中提取子序列:

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

4. 按长度降序排列子序列(即最长的在前)- 可以按 l 而不是 subseq.Count() 排序，但后者更具表现力，即使前者效率更高:

   orderby subseq.Count() descending
   

5. 计算每个子序列的总和，并对子序列进行排序，使最高值的总和排在最前面:

   orderby subseq.Sum() descending
   

6. 选择子序列:

   select subseq;
   

7. 只选择第一个子序列 - 它是具有最大长度的最高值和:

   xs.First();
   

希望这对您有所帮助。