What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing

[answerhappygod]

advertisement


var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
}
});
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}
a) O(n2)
b) O(n)
c) O(n3)
d) O(1)