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) {

}

}

РЕШЕНИЕ

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

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

Пусть x_i, …, x_j – искомая подпоследовательность. Тогда очевидно, что для всякого k (0 ≤ k < i) сумма чисел на промежутке x_k, …, x_{i - 1} отрицательна. Также для всякого p (j < p ≤ n – 1) сумма чисел на промежутке x_j+1, …, x_p отрицательна.

В переменной 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;

}

}