int max_sum_rectangle(int arr[][3],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
for(left = 0; left < col; left++)
{
for(right = left; right < col; right++)
{
if(right == left)
{
for(idx = 0; idx < row; idx++)
tmp[idx] = arr[idx][right];
}
else
{
for(idx = 0; idx < row; idx++)
tmp[idx] += arr[idx][right];
}
val = kadane_algo(tmp,row);
if(val > mx_sm)
mx_sm = val;
}
}
return mx_sm;
}
a) O(row*col)
b) O(row)
c) O(col)
d) O(row*col*col)
What is the time complexity of the following dynamic programming implementation of the maximum sum rectangle problem?
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
What is the time complexity of the following dynamic programming implementation of the maximum sum rectangle problem?
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!