algorithm - 我们如何输出标识最大子数组的索引 j 和 k

Question

最大子数组问题

给定一个包含 n 个整数的数组，找到子数组 A[j:k] 使总和最大化为

要求：我们如何输出标识最大子数组 A[j : k] 的索引 j 和 k

请帮帮我谢谢

标签： algorithm

Answer 1

您可以简单地使用最流行的算法Kadanes 算法。

正如算法所述，我假设传递给它的非空数组。然后我只需使用两个变量跟踪最大总和开始和结束的索引，prev并且curr

int maxsubarray(int arr[])
{
    int maxsofar = arr[0], sum = arr[0], prev = 0, curr = 0;
    for i = 1 to arr.size

      //number greater than the addition of sums
      if(nums[i] > sum + nums[i]) prev = i;

      //maximum sum till this point in the array
      sum = max(nums[i], sum + nums[i])

      // if this is better than what we have so far
      if(sum > maxsofar)
          //store this sum and the array value
          maxsofar = sum
          curr = i

    print "start index of sum:", prev
    print "end index of sum:", curr

    // return the maximum value also found so far
    return maxsofar;
}