Uva 787: Maximum subarray product
Feb 25, 2017 · 1 min read
PROBLEM link Uva1062
SUBMIT link Uva1062
Prerequisite
basic java Programming , ArrayList
Note
- this problem can’t not be solved by simple datastructure in C/C++ , so we have to use either Java BigInteger or Python
java solution is provided here.
Please not there that maximum product is required for consecutive elements only or subarrays.
Python Solution is invited by anyone.
Explanation
the most simple solution for this problem is to try all possible subarrays and find maximum product of them all.
total number of subarrays in n element arrays is O(n²) so time complexity will be O(n²),
we can also use better O(N) solution based on Kadane’s Algorithm as here at geeksforgeeks.org
we highly recommend you to try writing code your self using above explanation ,
before viewing code….
