53. Maximum Subarray

 

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

 

53. Максимальный подмассив

 

Найдите непрерывную последовательность чисел в заданном массиве (содержащую как минимум одно число), сумма элементов которой наибольшая.

Например, для массива [-2,1,-3,4,-1,2,1,-5,4] искомой подпоследовательностью будет [4,-1,2,1], ее сумма sum = 6.

 

// C++

class Solution {

public:

  int maxSubArray(vector<int>& nums) {

       

  }

};

 

// Java

public class Solution {

  public int maxSubArray(int[] nums) {

       

  }

}

 

РЕШЕНИЕ

последовательности

 

Анализ алгоритма

Пусть xi, …, xj – искомая подпоследовательность. Тогда очевидно, что для всякого k (0 ≤ k < i) сумма чисел на промежутке xk, …, xi - 1 отрицательна. Также для всякого p (j < pn – 1) сумма чисел на промежутке xj+1, …, xp отрицательна.

В переменной s накапливаем частичные суммы. Если на i-ой итерации s станет отрицательным, это означает что с числа nums[i] выгоднее начать новую подпоследовательность. Ответом на задачу будет наибольшее значение s на всех итерациях.

 

Реализация алгоритма

 

class Solution

{

public:

  int maxSubArray(vector<int>& nums)

  {

    int s = 0, max = -2100000000;

    for(int i = 0; i < nums.size(); i++)

    {

      if (s > 0) s += nums[i]; else s = nums[i];

      if (s > max) max = s;

    }

    return max;

  }

};

 

Java реализация

 

class Solution

{

  public int maxSubArray(int[] nums)

  {

    int s = 0, max = Integer.MIN_VALUE;

    for(int i = 0; i < nums.length; i++)

    {

      if (s > 0) s += nums[i]; else s = nums[i];

      if (s > max) max = s;

    }

    return max;

  }

}