FM's Devlog | My First Devlog!

· 11 min read
devlog

Note: This post was originally published on my previous blog and was imported here later.

NB: Scroll to the bottom for glossary

Prefix

This will be the first of hopefully many devlog(s). Today, I will talk about how I optimized a solution I made about 6 months ago for the problem “Best time to buy and sell”. The problem goes something like this:

Given a sequence of daily values (like stock prices), determine the best days to buy and sell to maximize the profit (i.e., the largest increase from a lower value to a higher value that occurs later in the sequence). For example, look at this input:

7
100 180 260 310 40 535 695

The solution should output:

5 7

Because buying at 40 and selling at 695 is the highest value you can get from the 7-day portfolio given.

Now that you understand the problem, here’s a background story. I made a solution about 6 months ago. Honestly, I was such a “newbie” to programming back then… On May 21, 2025, I revisited this problem and looked at my solution. It was very buggy, some edge cases weren’t even handled, and what I really noticed was that the solution runs in O(n^2).

So, I tried to make a solution that runs faster, handles all edge cases, and is better overall. So that’s the background of this post.

The Problem I’m Actually Solving

The problem I’m actually solving will have an input like so:

2
5
30 10 100 20 80
7
90 40 20 70 80

So the exact same but this time can handle multiple test cases.

Old Solution

Here’s my old solution:

#include <stdio.h>

int main()
{
    int T;
    scanf("%d", &T);
    int D;
    
    for(int i=0; i<T; i++) {
        int H;
        scanf("%d", &H); getchar();
        int P[H];
        
        for(int j=0; j<H; j++) {
            scanf("%d", &P[j]);
        }
        
        int maxProfit=0;
        int idxLow;
        int idxHigh;
        
        for(int j=0; j<H; j++) {
            for(int k=j+1;k<H;k++){
                if(P[k]-P[j]>maxProfit){
                    maxProfit=P[k]-P[j];
                    idxLow=j;
                    idxHigh=k;
                }
            }
        }
        if (maxProfit!=0) {
        	printf("Case %d: %d %d\n",i+1,idxLow+1,idxHigh+1);
		} else {
			printf("Case %d: %d %d\n",i+1,0,0);
		}
        
    }
    return 0;
}

First of all, jeez, my code was confusing. The variable names were so bad and the loops were confusing. The spacing was bad and I can talk a bunch more about how badly written this code is… However, that’s not why we’re here today.

Now, as I mentioned in the prefix, the first thing I saw was that the code runs in O(n^2). Let’s focus on this part of the code for now:

for(int j=0; j<H; j++) {
    for(int k=j+1;k<H;k++){
        if(P[k]-P[j]>maxProfit){
            maxProfit=P[k]-P[j];
            idxLow=j;
            idxHigh=k;
        }
    }
}

Those loops are “trying” to find the maximum difference between two elements in an array P, where the second element (P[k]) must come after the first element (P[j]). It also records the indices of these two elements.

However this code fails on multiple test cases such as when the array P is as follows:

10 20 30 40 1

Output: 5 5
4 5 6 3 1 2

Output: 5 6

New Solution

In the new solution I made, I use problem simplification for special cases so that in those cases, the time complexity is reduced and I don’t have to run my main logic. In some way this is basically me trying to do dynamic programming where I do pre-analysis, branching by structure, and short-circuiting.

Here’s what my new code looks like:

#include <stdio.h>
#include <stdbool.h>

/*
	DP:
	1. If arr is always decreasing -> output 0, 0
	2. If arr is always increasing -> output 1, days + 1
	3. Check if always increasing or decreasing while doing input (reduce loops)
*/

int main() {
	int n;
	scanf("%d", &n); getchar();
	
	for (int tc = 0; tc < n; tc++) {
		int days;
		bool valid = false; // always down
		bool alwaysUp = true; // always up
		
		scanf("%d", &days); getchar();
		int arr[days];
		
		for (int i = 0; i < days; i++) {
			scanf("%d", &arr[i]);
			
			if (i != 0) {
				if (arr[i] > arr[i-1]) {
					valid = true;
				} else if (arr[i] < arr[i-1]) {
					alwaysUp = false;
				}
			}
		}
		
		if (!valid) {
			printf("Case %d: %d %d\n", tc + 1, 0, 0);
			continue;
		}
		if (alwaysUp) {
			printf("Case %d: %d %d\n", tc + 1, 1, days + 1);
			continue;
		}
		
		int lowestIndexRes = 0;
		int highestIndexRes = 0;
		int lowestIndex = 0;
		int maxRange = -1;
		
		for (int i = 0; i < days; i++) {
			int range = arr[i] - arr[lowestIndex];
			if (range > maxRange) {
				maxRange = range;
				lowestIndexRes = lowestIndex;
				highestIndexRes = i;
			}
			
			if (arr[i] < arr[lowestIndex]) {
				lowestIndex = i;
			}
		}
		
		printf("Case %d: %d %d\n", tc + 1, lowestIndexRes + 1, highestIndexRes + 1);
	}
	return 0;
}

Yeah, I know it’s way longer than the old code, but this one has a much better time complexity. Let’s analyze the time complexity.

While taking the input, I do some checks if the array is always going up or down (which I think is really smart). This way, if the array is actually only going up or down, my code runs in O(1), aka constant time, which is insane. And I also think this is a way to implement heuristic-like thinking because in those special cases I know what the output has to be, so I can just do a check and immediately output a hard-coded answer for those cases.

Now those are for special cases, what about when the array is mixed (non-special) case? Well this one took me a while because I couldn’t think of any way where I can handle all cases in O(n). There’s a ton of ways to do it in O(n^2) but I don’t want that. I’ll show my previous attempt so you get what I mean by “all cases”:

#include <stdio.h>
#include <stdbool.h>

/*
	DP:
	1. If arr is always decreasing -> output 0, 0
	2. If arr is always increasing -> output 1, days + 1
	3. Search lowest index and highest index while doing input (reduce loops)
	4. If lowest index is at (days - 1) -> search for lowest index before days - 1 -> output new lowest index, new highest index
	5. If lowest index and highest index is not actually the highest range (example: 4 5 6 3 1 2), output should be 1 3 but current code shows 5 6.
	6. If lowest index is lower than highest index -> output lowest index, highest index
	7. If lowest index is higher than highest index-> search for highest index after lowest index
*/

int main() {
	int n;
	scanf("%d", &n); getchar();
	
	for (int tc = 0; tc < n; tc++) {
		int days;
		bool valid = false; // always down
		bool alwaysUp = true; // always up
		int lowestIndex = 0;
		int highestIndex = 0;
		
		scanf("%d", &days); getchar();
		int arr[days];
		
		for (int i = 0; i < days; i++) {
			scanf("%d", &arr[i]);
			
			if (i != 0) {
				if (arr[i] > arr[i-1]) {
					valid = true;
				} else if (arr[i] < arr[i-1]) {
					alwaysUp = false;
				}
				
				if (arr[i] < arr[lowestIndex]) {
					lowestIndex = i;
				}
				
				if (arr[i] > arr[highestIndex]) {
					highestIndex = i;
				}
			}
		}
		
		if (!valid) {
			printf("Case %d: %d %d a\n", tc + 1, 0, 0);
			continue;
		}
		if (alwaysUp) {
			printf("Case %d: %d %d b\n", tc + 1, 1, days + 1);
			continue;
		}
		if (lowestIndex < highestIndex) {
			printf("Case %d: %d %d c\n", tc + 1, lowestIndex + 1, highestIndex + 1);
			continue;
		}
		
		// find highest after lowest index
		highestIndex = lowestIndex + 1;
		for (int i = lowestIndex + 2; i < days; i++) {
			if (arr[i] > arr[highestIndex]) {
				highestIndex = i;
			}
		}
		
		printf("Case %d: %d %d e\n", tc + 1, lowestIndex + 1, highestIndex + 1);
		
		return 0;
	}
}

This code, however, as shown in the comment, fails on a test case like:

4 5 6 1 3 2

Output from code: 4 5 e
Expected output: 1 3

The e is just to show which print hits. This shows on test cases where the lowest index and the elements after that lowest index don’t actually give the highest range. But after about 1.5 hours of thinking, I got to this loop:

for (int i = 0; i < days; i++) {
	int range = arr[i] - arr[lowestIndex];
	if (range > maxRange) {
		maxRange = range;
		lowestIndexRes = lowestIndex;
		highestIndexRes = i;
	}
			
	if (arr[i] < arr[lowestIndex]) {
		lowestIndex = i;
	}
}

Here’s a breakdown for ya: First of all, the loop goes through all elements in the array arr. And the current day i is considered a potential day to sell.

int range = arr[i] - arr[lowestIndex];

range calculates the potential profit by calculating the current (sell price) minus the lowest (buy) price seen up to this point. If the range is higher than the current max range, then update the max range to be the current range. With this block of code:

if (range > maxRange) {
	maxRange = range;
	lowestIndexRes = lowestIndex;
	highestIndexRes = i;
}

However, remember that as we iterate we need to look out for new record-low prices. Thus I have this code:

if (arr[i] < arr[lowestIndex]) {
    lowestIndex = i;
}

Basically, it says, “if the price on the current day i, arr[i], is even lower than the price at our currently tracked lowestIndex, it means we’ve found a potentially better day to buy.”

Conclusion

This first devlog detailed my journey of revisiting an old competitive programming problem, “Best time to buy and sell,” and significantly optimizing my initial solution. By moving from a brute-force O(n^2) approach, which was also buggy and poorly written, to a more refined O(n) strategy, I not only achieved substantial performance gains but also improved code clarity and robustness.

The key to the new solution was twofold:

  1. Pre-emptive checks for special cases: Identifying always increasing or always decreasing sequences during the input phase allows for an immediate, correct answer. While reading the input is O(n), the decision-making for these specific patterns becomes O(1) after the input is read, significantly speeding up these scenarios.
  2. Efficient single-pass for general cases: For mixed sequences, the algorithm now iterates through the prices once. It cleverly maintains the lowest buy price found so far and calculates the maximum profit if selling on the current day. If a new lower buy price is encountered, it’s updated, ensuring that we are always considering the best possible buy point for future sell points.

This exercise was a great reminder of how much one can improve over time and the importance of revisiting old work with fresh eyes. It highlights that clean, efficient code often comes from iterative thinking, understanding time complexity, and a solid grasp of the problem’s core logic. It’s not just about finding a solution, but about finding an elegant and efficient one.

Postfix

And that wraps up my first devlog! It was quite a rewarding experience to not only solve the problem more efficiently but also to reflect on my own growth as a programmer. Looking back at old code can be cringeworthy, but it’s also a testament to learning and development.

I’m excited to continue this devlog series, sharing more challenges, solutions, and insights from my coding journey. Hopefully, this was an interesting read, and perhaps it might even inspire you to revisit some of your own past projects. Stay tuned for more!

Glossary

  • Algorithm: A set of rules or a step-by-step procedure for solving a problem or performing a computation.
  • Array: A data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
  • Big O Notation: A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it’s used to classify algorithms according to how their run time or space requirements grow as the input size grows.
    • O(n^2) (Quadratic Time): An algorithm whose execution time is directly proportional to the square of the input size (n). This often involves nested loops iterating over the dataset.
    • O(n) (Linear Time): An algorithm whose execution time grows linearly with the input size (n). This typically means the algorithm iterates through the input data once.
    • O(1) (Constant Time): An algorithm whose execution time is constant, regardless of the input size.
  • Competitive Programming: A mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications. Contestants are referred to as sport programmers.
  • Devlog (Development Log): A series of posts or entries chronicling the development process of a project, often a game or software.
  • Dynamic Programming (DP): An optimization technique where a complex problem is broken down into simpler subproblems. Solutions to subproblems are stored to avoid recomputation. The author mentions attempting a DP-like approach through pre-analysis and branching.
  • Edge Case: A problem or situation that occurs only at an extreme (maximum or minimum) operating parameter. Good software should handle edge cases correctly.
  • Heuristic Algorithm: An algorithm designed to solve a problem in a faster way when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. It’s often based on “rules of thumb” or educated guesses. The author likens their special case handling to this.
  • Index (of an array): A numerical value (usually starting from 0) that indicates the position of an element within an array.
  • Time Complexity: A measure of the amount of time an algorithm takes to run as a function of the length of the input. It’s often expressed using Big O notation.