CODEWITHSUNDEEP
algorithm
JustJohn
JustJohn

Reputation: 59

How does the max subarray problem have an optimal substructure?

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.

Upvotes: 1

Views: 367

Answers (1)

RBarryYoung
RBarryYoung

Reputation: 56725

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.

Upvotes: 2

Related Questions