'Kadane`s Algorithm' 태그의 글 목록

Kadane`s Algorithm

Diademata 2017. 8. 7. 22:26

2017. 8. 7. 22:26

Given array of integers, find the maximal possible sum of some of its k consecutive elements.

Example

For inputArray = [2, 3, 5, 1, 6] and k = 2, the output should be

arrayMaxConsecutiveSum(inputArray, k) = 8.

All possible sums of 2 consecutive elements are:

2 + 3 = 5;

3 + 5 = 8;

5 + 1 = 6;

1 + 6 = 7.

Thus, the answer is 8.

code>>

int arrayMaxConsecutiveSum(std::vector<int> inputArray, int k)

{

int max = 0;

for (int i = 0; i < k; i++)

max += inputArray[i];

int tmp = max;

for (int i = 1; i < inputArray.size() - k + 1; i++)

{

tmp -= inputArray[i - 1];

tmp += inputArray[i + k - 1];

max = std::max(tmp, max);

}

return max;

}