How does the max subarray problem have an optimal substructure?

1
votes

As I understand it you need a problem to have an optimal substructure for dynamic programming to be applicable.

Here's what I don't get.

Take the following Array

A = [1, 6, -3, 1, 5, -1]

As per wikipedia:

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.

Here's where my confusion lies.

If I was asked to find the max subarray of size 3 in the array presented above the answer would be 1, 5, -1 (total sum 5).

But if I were to find the max subarray of size 2 the answer would be (1,6) which has no shared elements with the previous answer.

I must not be understanding what optimal substructure means but I don't see how.

1
algorithm
Greedy algorithms don't necessarily have an optimal substructure. - nice_dev
The key word is "subproblem". Start by designing a brute force algorithm to solve the problem. Then analyze the brute force algorithm to determine whether it is solving the same subproblems over and over again. If so, then the algorithm is a candidate for dynamic programming. The brute force solution for the max subarray problem is a simple O(n) sliding window. And O(n) is the theoretically best time for that problem, so dynamic programming has no possible benefit. - user3386109

1 Answers

2
votes

Here the overlapping subproblems are not the subarray lengths, but the containing array lengths. Thus if F(i:j, s) gives the maximum value subarray of length s in the containing (sub)array from index i to index j, then we can show that

F(0:k, s) = Max( F(0:k-1, s), F(k-s+1:k, s) )

which is overlapping optimal substructure.