Given an array A1 n as input is there an On time algorith

Given an array A[1 · · · n] as input, is there an O(n) time algorithm that ndj (1 j n) such that A[1] + A[2] + · · · + A[j] is maximized? You can simply say ‘true’ or‘false.’ No justication is needed.

Solution

TRUE


There exists.

Calculate sum of all the elementS:-

A[i] will keep elemnets from 0 to i ...A[N] will contains sum from 0 to N
Now try to maximize it : Bsically it is trying to find the Maximum sum subarray. SO Yeah we can do it in O(N) time.


Answer is YES

Thanks, let me know if there is any concern.