Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
(a) Dynamic programming
(b) Two for loops (naive method)
(c) Divide and conquer
(d) Dynamic programming, naïve method and Divide and conquer methods
I have been asked this question in an internship interview.
Question is taken from Maximum Sum of Continuous Subarray in chapter Dynamic Programming of Data Structures & Algorithms II