MadeEasy Test Series: Algorithms - Dynamic Programming

Question

Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum.

Eg. [-2, 11, -4, 13, -5, 2] → 20

If dynamic programming approach is used then what is time complexity and space complexity?

(a.) O(n3), O(1)

(b.) O(n), O(n)

(c.) O(n3), O(n)

(d.) O(n2), O(1)

Given answer is option (b.)

Answer 1

The algorithms is a standard dynamic programming algorithm (Kadane's algorithm)

In this we calculate the maximum possible sum ending at each index i and then find the maximum among those.

int max_sum = INT_MIN; // denotes the maximum possible sum of subarray

    int max_sum_ending_here = 0; // denotes the maximum possible sum ending at index i

    for(int i = 0; i < a.size(); i++)
    {
        max_sum_ending_here = max(a[i], a[i] + max_sum_ending_here);
        if(max_sum_ending_here > max_sum) max_sum = max_sum_ending_here;
    }
 

Comments

Space complexity should be O(1) because we are using variables only.