Please solve both problems. The first problem is simply true or false, but pleas
ID: 3794801 • Letter: P
Question
Please solve both problems. The first problem is simply true or false, but please explain if possible.
Given an array A[1. .. n] as input, is there an O(n) time algorithm that find j (1 lessthanorequalto j lessthanorequalto n) such that A[1] + A[2]+. .. + A[j] is maximized? You can simply say 'true' or 'false' No justification is needed. We're given an array of n numbers, A[1. .. n] and want to add up the n numbers. Let's consider the following divide-and-conquer algorithm: It partitions the array into two subarrays, A[1. .. n/2] and A[n/2 + 1. .. n] and recourse on them to compute A[1] +. .. + A[n/2], and A[n/2 + 1] +. .. + A[n]. Then it adds up the two sums and return the value. What is the recurrence for the running time? Solve it.Explanation / Answer
1) True
You can simply use one extra array say sum.
sum[0] = a[0]
max = a[0]
maxindex =0
for(i:1 to n)
sum[i] = sum[i-1] + a[i]
if sum[i] > max
max = sum[i]
maxindex = i
2) Recurrence is : T(n) = T(n/2) + T(n/2)
By solving running time will be O(n).
It will go to each and every element that's why time complexity is O(n)