2
$\begingroup$

I read the question in Exercise 4.1-4 in Introduction To Algorithms:

Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

I cannot get what's an empty sub-array.

I came across the point that a single number can be returned if the array consists of negative elements only.

Please can anyone explain the concept of an empty sub-array? And how can we have an empty sub-array?

Even if a single element is returned it still means that sub-array is not empty. Please clear the doubt.

Edit:

To make it more clear as a question if I take an array of elements:

[-3,-4,-1,-8]

The answer would be -1 or 0? Please explain if why it should be 0 and how can we conclude an empty sub-array.

Thank you.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Look at an 'array' as an object, on which we can apply two operations: 1. Read from some of its indices, and 2. Get its length. (In fact this is how an array is treated in many languages) And there's an obvious criterion on these operators: you can not read an out of bounds index. So an empty array is just an array of length 0, so it has no possible 'inside bounds' indices, thus you can't just read anything from it. $\endgroup$
    – Beleg
    Jun 22, 2020 at 9:16
  • 1
    $\begingroup$ For example, see how arrays are implemented in C: they are just pointers. We just allocate memory from where it's pointing to a determined 'length'. You can read/write anywhere in your allocated memory, but you'll only consider it to be your array if it is between that pointer and where it ends. So you have a pounter, you allocate 5 words of memory where its length is 5, and you allocate 0 words (i.e. none) when its empty. $\endgroup$
    – Beleg
    Jun 22, 2020 at 9:31
  • $\begingroup$ Yeah I know that but I cannot understand relevance of empty sub-array in the question and how to return the empty sub-array. $\endgroup$
    – Sachin Bahukhandi
    Jun 22, 2020 at 10:25
  • 1
    $\begingroup$ An even harder or more general situation may help you understand one particular situation. Let us define the directed length of a subarray that starts at index $i$ and ends at index $j$ as $j-i-1$. Now we will even have subarrays of negative lengths. We can ask, what is the maximum net profit you can accumulate with a subarray of directed length no less than $-5$? $\endgroup$
    – John L.
    Jun 22, 2020 at 13:38

2 Answers 2

Reset to default
2
$\begingroup$

If you have this array: $[-2,-10,-5]$, and the problem specifies that you should return to it the sum of the maximum subarray whose length is at least $1$, you will return the sum of the subarray $[-2]$, which is $-2$. So far so good?

Now, focus here because this is where you are most probably having trouble:

The problem is now tweaked. The problem now allows you to return to it an empty subarray, which means, you can return to it a subarray that is empty - a subarray that has no elements. Bear with me:

In mathematics, an "empty sum" is a summation where the number of terms is zero. Verify.

Similarly, in computer science, an "empty subarray" is a subarray in which the number of terms is zero. This is just the definition. It's just a subarray whose sum evaluates to zero.

Now, concerning the tweaked version of the problem, what would be better, returning to it $[-2]$ whose sum evaluates to $-2$, or returning the empty subarray $( [ \ \ \ ] )$ whose sum evaluates to $0$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Okay the empty subarray should be returned if all the elements are negative and it's just a tweak but originally the problem would have returned -2 right? $\endgroup$
    – Sachin Bahukhandi
    Jun 22, 2020 at 12:22
  • $\begingroup$ The original problem will indeed return $-2$. $\endgroup$
    – einstein
    Jun 22, 2020 at 12:27
2
$\begingroup$

A subarray of length zero is empty.

Given an array $A[1],\ldots,A[n]$, a subarray is specified by a pair of indices $i \leq j$. These correspond to the subarray $A[i],\ldots,A[j]$ of length $j-i+1$. If we also allow $j = i-1$ then we get an empty subarray of length $j-i+1 = 0$, whose sum is zero.

In the maximum subarray problem, we are given an array $A[1],\ldots,A[n]$, and want to find a subarray whose sum is maximal. If we don't allow empty subarrays, this means that we are looking for the maximum value of $$ A[i] + \cdots + A[j], $$ where $1 \leq i \leq j \leq n$. If we are allowing empty subarrays, then we take the maximum of that with $0$, which is the sum of the empty subarray.

This only makes a difference if all entries of the array are negative. The maximum sum of a non-empty subarray is in this case the maximal element $A[i]$, which is the sum of the subarray $A[i]$ of length $1$. The empty subarray, however, has a larger sum: $0$. Therefore if the empty subarray is not allowed, the answer should be $\max_i A[i]$, and if it is allowed, the answer should be $0$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Then according to the question how is it possible for us to think of the result as an empty sub-array. An empty sub-array has zero elements and even if we find the least negative element it would still be a sub-array of length 1. Correct me if I am wrong. Question detailed here: atekihcan.github.io/CLRS/E04.01-04 $\endgroup$
    – Sachin Bahukhandi
    Jun 22, 2020 at 10:24
  • 1
    $\begingroup$ I'm not sure what the maximum subarray problem is – guessing that you're looking for the subarray with maximum sum. If you allow empty subarrays, then when all elements are negative, the answer would be zero (compared to the maximal element, which is what you get without empty subarrays). $\endgroup$
    – Yuval Filmus
    Jun 22, 2020 at 10:26
  • $\begingroup$ Right. I am looking for the maximal element and I cannot understand what allowing empty sub-array means. $\endgroup$
    – Sachin Bahukhandi
    Jun 22, 2020 at 10:31
  • $\begingroup$ I have also edited the question to make it more clear on what I do not understand. $\endgroup$
    – Sachin Bahukhandi
    Jun 22, 2020 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.