给定一个整数数组.找到MAXIMUM总和最大的子阵列

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

希望这可以帮助.

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

Update1:添加了打印子阵列索引的代码.

Update2:如果找到两个具有相同总和的子数组,请选择具有更多元素的子数组.

Update3:修复导致负数的算法