In this video, we will be developing both false solutions.

In many, but not all cases,

it is going to be too slow to be accepted.

Still, such a solution is useful for

understanding the problem statement and for debugging other solutions.

Hopefully, there are two types of problems.

Problems of the first type ask you to find

an object on some set A satisfying a certain property.

Problems of the second type ask for an object of some set

A optimizing the value of a certain objective function.

The set A is called a search space.

Let me illustrate this notion on a several examples.

You're given m strings and an integer n. The goal is to

find a string of length m which contains all givens strings as substrings.

We will consider this problem for the strings consisting of letters a and b.

This is a problem of the first type.

You are asked to find an object with the given the property,

namely a string containing all given strings.

Let's look at an example.

We are given two strings, ab and ba,

and the required length of the substring is three.

There are two possible outputs.

The first one is aba, which starts with ab and ends with ba.

The second one is bb,

which starts with ba and ends with ab.

We'll solve the superstring problem by tying

all strings of length n consisting of letters a and b.

For each string, we will check if it contains all given strings.

The search space here is the set of

all strings of length n consisting of letters a and b.

Let's see how it works on another example.

Let n equals four and two given strings are bab and abb.

For each of the four symbols of the required superstring,

there are two choices,

and that's why there are two to the fourth or 16 strings in the search space.

Let's look at them. Now we see all the elements of the search space.

For each of them, we've checked if it contains bab and if it contains abb.

We see that the only string on the search space which contains both is babb.

Therefore, it's the only possible output for this example.

We can see that in another problem.

We were given an array and are asked to find a subarray with the largest sum.

If all elements of the array were non-negative,

we could instantly take the whole array is answered.

But if an array is allowed to contain negative elements,

this solution will not work.

Let's take a look at the example.

We see that maximum subarray can include negative numbers.

Here it's more profitable to take minus two and three,

but it's unprofitable to take minus 10 and five.

Thus, this problem is not completely straightforward.

But let's try our technique on it.

This is a problem of the second type.

We are asked to maximize the objective function.

The search space is easier to determine.

It's all subarrays of the given array.

It's useful to identify a subarray with positions of its first and last elements.

Since we understand what the search space is, we are almost done.

And given array of possible first,

last element space, compute the sum of the elements of the corresponding subarray.

From each pair, take the maximum, and this is it.

Recall the Robber's problem for the previous video.

Let's give a fuller definition of this problem.

We are given n items with weights from w_1 to w_n and costs from c_1 to c_n.

The task is to find the largest total cost

of the set of items which satisfies the weight limit.

Recall the example from the previous video.

We have three objects.

And instead of taking the first two of them as we tried to do in the first video,

the optimal weight to peg the backpack is to put the third item into it.

Let's determine the search space for the Robber's problem.

It's natural to define it as the set of all possible sets of items.

We will associate items with their numbers.

And for our example,

there are eight possible sets listed on the slide.

To solve the problem, we simply iterate through all search sets.

For each set, we first check whether it's total weight is smaller than the given limit.

If it is, we compute its total cost and update the answer if needed.

Let's summarize the observations.

For the superstring problem,

the search space consists of strings of length n consisting of letters a and b.

For the Robber's problem, it consists of all possible sets of items.

And for the maximum subarray problem,

it consists of all subarrays or equivalently of pairs (l, r).

For the maximum subarray problem,

the solution is clear since we understood what the search space is.

We go through all pairs l and r with two nested two nested for cycles,

compute the objective function for each pair,

and take the maximum.

For the superstring problem,

it's not that easy.

You have to go through all strings of length n. That could be

implemented using n nested for cycles iteration over the set of letters a and b.

In the imaging of pseudo language,

the code look like this.

Each cycle enumerate corresponding symbol of a string.

And when they're all fixed, we check the property.

Unfortunately, you can't write this in

the real programming language because you don't know the exact number of nested cycles.

In the next video, we will understand how to simulate n nested for cycles using location.

This will allow us to implement a solution

for the superstring problem and for the Robber's problem.