KADANE'S ALGORITHM AND BASIC TIME COMPLEXITY
Hello! My name is Milkeles and in this short tutorial I'll show you a way to find the maximum subarray in an array of elements.
Who's this tutorial for? Although this tutorial may be helpful to almost everyone, you're expected to at least know the basics of scripting in Lua, especially loops, before you dive into this. The topic of this tutorial is not something crucial, in fact, you'll likely never use this in game development. What you will need to develop games, however, is decent problem-solving skills and the purpose of this tutorial is to help you improve yours a little. Also, we will cover the basics of a very important concent in programming - time complexity. For those who decide to stay regardless of what I just said, have fun. :)
What's a subarray? A subarray is an array within another array. A subarray is not necessarily smaller than the original array, for example, the subarray of [1, 2, 3, -4, 5] could be [2, 3, -4], but it could also be [1, 2, 3, -4, 5], or even a single element - [3]. However, it cannot be [2] and [-4], the elements need to be contiguous/neighboring.
What's the problem? Let's take the same example, if we want to find the maximum subarray of [1, -3, 2, 1, -1], it would be [2, 1], because 1 + 2 = 3 and there is no way to form any other subarray that has larger sum. It is easy to tell, but how can we do this with code?
Brute-force solution. Naturally, most people would simply try to find all the sums of all possible subarrays with a nested loop:
arr = {1, -3, 2, 1, -1}
maxSum = -math.huge --It is possible the max subarray may have a sum less than 0.
for (i = 1, #arr, 1) do
local currentSum = 0
for(j = 1, #arr, 1) do
currentSum = currentSum + arr[j]
end
if (currentSum > maxSum) then
maxSum = currentSum
end
end
What it does is that it checks the sum of all possible combinations: [1], [1, -3], [1, -3, 2], [1, -3, 2, 1], [1, -3, 2, 1, -1], [-3, 2, 1, -1], [2, 1, -1], and so on. This solution WILL work and for small arrays like this it will be very fast, we only need to conduct total of 25 calculations and the computer can do that instantly. However, if our array had 10 000 elements, that would mean we have to perform 100 000 operations and, while that will also take mere seconds for the computer, if we want our code to be as fast as possible, that will not be the best possible way to solve the problem.
Note: This is not the main purpose of this tutorial, but I'd like to deviate a little from the topic and explain how time complexity works. You may skip this if you're familiar, but many Roblox and indie developers are not.
Estimating the time our code takes to run, and especially improving that, is extremely important in games as performance is often crucial but, also often, have to use many loops, especially nested ones, or other heavy operations all the time. Estimating how fast a certain code is can be a bit challenging and difficult to comprehend, so we will not go into details in this tutorial, we'll only scrape the surface, so that you'll have a basic understanding of it and you'll hopefully able to understand why the brute force solution above is not an optimal one. So, what is time complexity after all? When we measure time complexity of a code, we don't actually measure it in units of time, such as miliseconds or seconds, because our computers nowadays perform hundreds of operations behind the scenes, and those operations affect our measurements significantly and every time we measure the time it takes our code to run, the result will be different. Of course, we could measure it several times and calculate the average time, but that's time-consuming and often inaccurate as well. Instead of time units, we use what's so called "steps", each step is a single operation our code has to perform. For example in the following code has total of 3 steps:
a = 1
b = 2
print(a + b)
The steps are - initialize a with 1, initialize b with 2, print the sum of a and b. This code will always take that many steps to compute, therefore, it's time complexity is constant. There are three different kinds of time complexities - average (Θ), best (Ω), and worst(O). We usually care about the worst possible case, but knowing the other two is helpful in many cases too. Our code above takes 3 operations and that is a constant time, it will always take that many operations, it cant get any better or worse, so we say that it's time complexity is O(3) (Big-Oh of 3) = Θ(3) = Ω(3). That's constant time complexity, if our code has constant time complexity, that's great, there's nothing to worry about, but we cannot always write code that way...
Imagine you have a list of things to do and it takes you certain amount of time to do each. Linear time complexity means that the time it takes to process the list grows proportionally with the size of the list. If you have twice as many items, it will take roughly twice as much time. In a loop, if you go through each item in a list exactly once, the loop has linear time complexity. For example, if we have an array of n numbers and we want to print each number, that will take us n steps, therefore the time complexity of our loop is O(n), we don't care (or know) about the exact count of elements, we just say that it is n. Linear time complexity is also good, it is very fast, not as fast as constant time complexity, but it would never crash our computers if what we're trying to do is physically possible for our computer to handle. That is not the case with nested loops, however:
Exponential time complexity If we have a loop that runs n times, and inside it another one that runs m times, this means that for every iteration of the first, the second loop will run m times, therefore the complexity of our code is O(n×m). If both of the loops run n times, we have complexity of O(n^2), because n×n = n^2. This is still fine but only for small or medium programs, but you have to understand that it's N TIMES WORSE than the linear time, making it very slow. And if we put a third loop inside the second we get time complexity of O(n^3), which is catastrophic. For comparison, if code runs with O(n) time it would be able to process 1 million pieces of data, O(n^2) - 10K pieces of data, O(n^3) -> 100 pieces of data. And it gets worse and worse, that's why we MUST avoid writing code with exponential time complexity. (Although sometimes we can't, that's why NP-hard problems like the Hanoi towers one exist).
Logarithmic time complexity This kind of time complexity is more difficult to comprehend, and yet we'll need it for our original problem. Imagine you want to find a particular word in a dictionary, if you skim through the pages one by one, it will take you a long time (O(n) operations, to be exact). However, words in a dictionary are ordered alphabetically, so you can open it in the middle then tell in which half your word is, then open in the middle of that half, then again, and again, until you eventually find the page where the word you're looking for is. Esentially, you're eliminating half of the problem each time, and that's what logarithmic time is. O(logn) IS BETTER THAN O(n) AND WORSE THAN O(const).
Here I explained the basics of time complexity, I only used worst-time complexity because it is most important and we don't want to go into details, but if you'd like to learn more there's also a similar way to measure the amount of data your code uses - space complexity, and there are cases when the best, worst, and average time complexity are not the same for a single piece of code.
ANSWERS
array = { 1, -3, 1, 2, -1 } -- An example, you can use anything else.
-- Taking the first element as the max subarray and the current max subarray.
max = array[1]
currentMax = array[1]
-- Starting from the second element because we already checked the first.
for (i = 2, #array, 1) {
--Comparing the current element and the previous max combined with the current element.
currentMax = math.max(array[i], currentMax + array[i])
--Replacing the previous max if the current one is larger.
if (currentMax > max) then
max = currentMax
end
}
print(max)