Question: 2. What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?<div class="hk1_style-wrap4"><div class="hk1_style-wrap3"><div class="hk1_style-wrap2"><div class="hk1_style-wrap"><div class="hk1_style"><div class="cpp"><pre class="de1"><span class="co2">#include&lt;stdio.h&gt;</span> <span class="kw4">int</span> max_num<span class="br0">(</span><span class="kw4">int</span> a,<span class="kw4">int</span> b<span class="br0">)</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>a<span class="sy1">&gt;</span> b<span class="br0">)</span> <span class="kw1">return</span> a<span class="sy4">;</span> <span class="kw1">return</span> b<span class="sy4">;</span> <span class="br0">}</span> <span class="kw4">int</span> maximum_subarray_sum<span class="br0">(</span><span class="kw4">int</span> <span class="sy2">*</span>arr, <span class="kw4">int</span> len<span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> sum<span class="br0">[</span>len<span class="br0">]</span>, idx<span class="sy4">;</span> sum<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span> <span class="sy1">=</span> arr<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="sy4">;</span> <span class="kw1">for</span><span class="br0">(</span>idx <span class="sy1">=</span> <span class="nu0">1</span><span class="sy4">;</span> idx <span class="sy1">&lt;</span> len<span class="sy4">;</span> idx<span class="sy2">++</span><span class="br0">)</span> sum<span class="br0">[</span>idx<span class="br0">]</span> <span class="sy1">=</span> max_num<span class="br0">(</span>sum<span class="br0">[</span>idx <span class="sy2">-</span> <span class="nu0">1</span><span class="br0">]</span> <span class="sy2">+</span> arr<span class="br0">[</span>idx<span class="br0">]</span>, arr<span class="br0">[</span>idx<span class="br0">]</span><span class="br0">)</span><span class="sy4">;</span> <span class="kw4">int</span> mx <span class="sy1">=</span> sum<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="sy4">;</span> <span class="kw1">for</span><span class="br0">(</span>idx <span class="sy1">=</span> <span class="nu0">0</span><span class="sy4">;</span> idx <span class="sy1">&lt;</span> len<span class="sy4">;</span> idx<span class="sy2">++</span><span class="br0">)</span> <span class="kw1">if</span><span class="br0">(</span>sum<span class="br0">[</span>idx<span class="br0">]</span> <span class="sy1">&gt;</span> mx<span class="br0">)</span> mx <span class="sy1">=</span>sum<span class="br0">[</span>idx<span class="br0">]</span><span class="sy4">;</span> <span class="kw1">return</span> mx<span class="sy4">;</span> <span class="br0">}</span> <span class="kw4">int</span> main<span class="br0">(</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> arr<span class="br0">[</span><span class="br0">]</span> <span class="sy1">=</span> <span class="br0">{</span><span class="sy2">-</span><span class="nu0">2</span>, <span class="sy2">-</span><span class="nu0">5</span>, <span class="nu0">6</span>, <span class="sy2">-</span><span class="nu0">2</span>, <span class="nu0">3</span>, <span class="sy2">-</span><span class="nu0">1</span>, <span class="nu0">0</span>,<span class="sy2">-</span><span class="nu0">5</span>, <span class="nu0">6</span><span class="br0">}</span>, len <span class="sy1">=</span> <span class="nu0">9</span><span class="sy4">;</span> <span class="kw4">int</span> ans <span class="sy1">=</span> maximum_subarray_sum<span class="br0">(</span>arr, len<span class="br0">)</span><span class="sy4">;</span> <span class="kw3">printf</span><span class="br0">(</span><span class="st0">"%d"</span>,ans<span class="br0">)</span><span class="sy4">;</span> <span class="kw1">return</span> <span class="nu0">0</span><span class="sy4">;</span> <span class="br0">}</span></pre></div></div></div></div></div></div>
Options:
O(n)
O(logn)
O(nlogn)
O(n2)
Answer: A