Given an array A containing N real numbers – positives, negatives as well as zeros. The goal is to find indices p and q in the array such that
i = q
Σ A[i] is maximized and q ≥ p ≥ 0
i = p
Develop a program which reads N from user, generates a random array of N real numbers – positives, negatives and zeros, and finds the values of p and q which satisfy above maximization.
Constraints : (i) N has to be read from user and memory for array has to allocated dynamically. Array will be populated with positive, negative and zero real numbers randomly.
(ii) The program will print the array and will also print the values of p and q and the value of maximized summation. (iii) The algorithm for finding p and q will run in O(N2) time and O(N) space, at most.