maximum subarray

[AlphabetsAlphabets]

Notes on the maximum subarray question. The video by Byte by Byte helped me the most.

The solution is by using a sliding window. This is a dynamic sliding window as the length subarray changes on both the head and tail.

[AlphabetsAlphabets]

My solution was the brute force approach. I wasn't able to figure out the implementation and it wasn't going to work regardless. This is the python solution translated.

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let len = nums.len();
        let mut ans = 0;
        for i in 0..len {
            let mut cur_sum = 0;
            for j in i..len {
                cur_sum += nums[j];
                ans = std::cmp::max(ans, cur_sum);
            }
        }

        ans
    }
}

The solution falls apart with a simple example due to how it works. Below is a simple illustration.

Imagine the following array and assume that a is required for the answer to be valid but the summing of b into it would result in a smaller sum. This means that b needs to be skipped over.

[a, b, c, d]

The the way the algorithm works it "forgets" the things on the left, which means that despite needing a it is ignored.

[AlphabetsAlphabets]

The one I understood was a video by NeetCode. It uses the sliding window technique. My original implementation was to use slice::windows. Turns out I was over complicating things. The main idea is to ignore any sums where the result is negative as they don't contribute but take away from the maximum sum.

    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sub = nums[0];
        let mut cur_sum = 0;
        for value in nums {
            if cur_sum < 0 {
                cur_sum = 0;
            }

            cur_sum += value;
            max_sub = std::cmp::max(max_sub, cur_sum);
        }

        max_sub
    }

This is the solution. The idea behind it is to ignore any negative sums as negative sums don't contribute so simply reset it back to zero. Then check to max_sub against cur_sum to see which is larger.

This was my original implementation.

    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut sum = 0;
        for value in nums {
            if value < 0 {
                sum = 0;
                continue;
            }

            sum += value;
        }

        sum
    }

The problem begins with not separating the maximum sub array from the current sum. Why? If sum = 0 is ran then the sum would just be reset. There would be no "saving" of the correct answer before it was reset.

-2, 1, -3, 4, -1, 2, 1, -5, 4

In this array. -2 is correctly skipped. When value = -3, sum = 1. So, sum = 0 and moves onto the next iteration. This continues until value = 2 where sum = 2 and for value = 1, sum = 3. It sees -5, resets and since there are no more values 4 becomes the max. Which resulted in this implementation.

    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sum = 0;
        let mut cur_sum = 0;
        for value in nums {
            if value < 0 {
                cur_sum = 0;
                continue;
            }

            cur_sum += value;
            max_sum += std::cmp::max(max_sum, cur_sum);
        }

        max_sum
    }

The issue with this is line.

max_sum += std::cmp::max(max_sum, cur_sum);

Given that it is additive, max_sum can only get bigger and bigger. It shouldn't be max_sum += but rather max_sum =. But this has the same resetting problem and ultimately max_sum = 4. Which lead to this implementation.

    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sum = 0;
        let mut cur_sum = 0;
        for value in nums {
            if value < 0 {
                cur_sum = 0;
                continue;
            }

            cur_sum += value;
            max_sum = std::cmp::max(max_sum, cur_sum);
        }

        max_sum
    }

There are still problems. With the continue value accumulation occurs again where max_sum is again 4. Removing it doesn't solve all it either.

    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut max_sum = 0;
        let mut cur_sum = 0;
        for value in nums {
            if value < 0 {
                cur_sum = 0;
            }

            cur_sum += value;
            max_sum = std::cmp::max(max_sum, cur_sum);
        }

        max_sum
    }

These are the iterations:

max_sum: 0. cur_sum: -2
max_sum: 0. cur_sum: -1
max_sum: 0. cur_sum: -3
max_sum: 1. cur_sum: 1
max_sum: 1. cur_sum: -1
max_sum: 1. cur_sum: 1
max_sum: 2. cur_sum: 2
max_sum: 2. cur_sum: -5
max_sum: 2. cur_sum: -1

I'm not sure why this happens. I spent so long but couldn't understand why max_sum is never 4.

The finaly problem is with value < 0 it should be cur_sum < 0. By making the change things worked out. Because if cur_sum is negative it doesn't contribute to the maximum sum. By reseting cur_sum to 0 it also starts the new sub array.

A final change is max_sum = nums[0]. Given that negative values exist at at the call to max it would always choose 0. In the case of a fully negative array the smallest negative number is always less than 0. Therefore the output is 0 and wrong.