Please solve both problems The first problem is simply true

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.

Solution

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)