MCQ Practice

What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum? #include int max_num(int a,int b) { if(a> b) return a; return b; } int maximum_subarray_sum(int *arr, int len) { int sum[len], idx; sum[0] = arr[0]; for(idx = 1; idx < len; idx++) sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]); int mx = sum[0]; for(idx = 0; idx mx) mx =sum[idx]; return mx; } int main() { int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }

A

O(n)

B

O(logn)

C

O(nlogn)

D

O(n 2 )

Correct Answer: A