查找数组中连续随机数的最大和

本文关键字：随机数 数组 连续 查找 | 更新日期: 2023-09-27 18:30:36

>我有一个介于 -100 和 100 之间的 25 个随机整数的数组。

例如，我的数组可能如下所示：-10， 23， 19

， -11， 3， -9， -8， 4， 10， 20， 30， 40， 50， -6， -2， 1， -9， 8， -6， 20， -21， -3， -2， -4， -7

我希望编写一个方法，该方法接收我的数组作为参数，并打印出以下内容：第一个索引，最后一个索引以及它们之间的连续元素的总和，这将给出可能的最大总和。

对于我的示例，输出将是：第一个索引：1（值：23），最后一个索引：19（值：20），总和：177

我不知道我应该如何处理这个问题。我写了一个代码，但它非常复杂且效率低下，因为我使用列表来存储所有可能的总和。你能展示这个问题的伪代码，或者 c# 中的代码吗？

查找数组中连续随机数的最大和

这是文献中一个众所周知的问题，被称为（在许多其他名称中）最大子数组问题。您可以在此处找到更多信息以及带有可能解决方案的伪代码：http://en.wikipedia.org/wiki/Maximum_subarray_problem

由于您的问题似乎是找到可行的算法而不实现它，因此以下伪代码应该就足够了：

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

您不需要保留所有可能的金额，因为您只对最大的金额感兴趣。

遍历组合，并查找大于目前总和的任何总和。

您可以利用以下事实：任何元素范围的总和是不包括最后一项加上最后一项的元素的总和。即，您不需要遍历元素来计算每个可能的总和，因为您已经拥有了一个元素的范围总和：

public static void ShowLargestSum(int[] arr) {
  int largest = arr[0], start = 0, end = 0;
  for (int i = 0; i < arr.Length; i++) {
    int sum = 0;
    for (int j = i; j < arr.Length; j++) {
      sum += arr[j];
      if (sum > largest) {
        largest = sum;
        start = i;
        end = j;
      }
    }
  }
  Console.WriteLine("first index: {0} (value: {1}), last index: {2} (value:{3}), total sum: {4}", start, arr[start], end, arr[end], largest);
}

在我的计算机上为您的示例数组执行时间：0.17 毫秒。

相关文章：