recategorized by
3,831 views

3 Answers

1 votes
1 votes

Option B is the Correct Answer.

Kadene algorithm is used to find maximum sum subarray in an array. It is also known as maximum subarray problem.

Time Complexity: O(n)
Algorithmic Paradigm: Dynamic Programming

Kadane’s Algorithm:

  Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Explanation:

Kadane's algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position i (call this $B_{i}$), what is the maximum subarray sum ending at position i+1(equivalently, what is $B_{i+1}$)? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix, or it doesn't (equivalently, $B_{i+1}$ = max ($A_{i+1}$ , $A_{i+1}$+$B_{i}$), where $A_{i+1}$ is the element at index i+1).

 Kadane's algorithm is based on splitting up the set of possible solutions into mutually exclusive (disjoint) sets. We exploit the fact that any solution (i.e., any member of the set of solutions) will always have a last element  i (this is what is meant by "sum ending at position i "). Thus, we simply have to examine, one by one, the set of solutions whose last element's index is 1, the set of solutions whose last element's index is  2, then 3, and so forth to n. It turns out that this process can be carried out in linear time.

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far .

                                kadane-algorithm

1 votes
1 votes
Kadane algorithm is used to find the maximum sum subarray in an array.

It used dynamic programming and time complexity is $O(n)$

So B is correct.
0 votes
0 votes

Kadane algorithm is used to find the maximum sum subarray in an array. It runs in O(n) time complexity Implementation in python:
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far

Answer:

Related questions

4 votes
4 votes
3 answers
4