Maximum Subarray

This is a LeetCode easy problem. The subarray is contiguous. There is also the maximum sum problem, but that’s easy, just add all positive values. https://www.youtube.com/watch?v=86CQq3pKSUw&ab_channel=CSDojo

https://leetcode.com/problems/maximum-subarray/

The main thing is figuring out this recurrence relation

dp[i] = max(dp[i-1] + nums[i], nums[i]);

My solution

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int dp[n];
    dp[0] = nums[0];
    for (int i=1;i<n;i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
    }
    return *max_element(dp, dp+n);
}

• Note that dp[i] can simply be replaced by a single variable, but dp[i] represents the longest subarray sum up to index i

Explanation

With brute force, you can figure out a $O(n^3)$ solution, and you can optimize it to $O(n^2)$ (by traversing all possible subarrays)

For out a $O(n)$ solution. But this is just about breaking down a big problem into a smaller problem

Motivation: $dp[i]$ represents the largest subarray that ends on index $i$. There are only 2 possibilities:

1. An array of single element, i.e. dp[i] = nums[i]
2. Otherwise, since it spans multiple elements, dp[i] = nums[i] + dp[i-1]

We can just take the maximum, i.e.

dp[i] = max(nums[i], dp[i-1] + nums[i])

NOTE that this would be incorrect:

dp[i] = max(dp[i-1], dp[i-1] + nums[i])

• If we did this, it would result in incorrect updates, consider [1, -1, 3] would give 4 even though the answer is 3
• This equation means something completely different, the largest subarray seen so far is either the previous one, or the previous one concatenated with the current one
• But then you lose the promise of contiguity because dp[i] no longer represents the largest subarray sum INCLUDING i
• NOTE that this works for subset array (more below), but it’s missing nums[i] (you actually have 3 choices)

You code up an iterative solution.

Largest subset sum

very easy to confuse the logic.

Writing a note after CP Brainfarts on a similar problem but that DOESN’T ask for largest subarray sum, but rather largest subset sum on odd indices!

Subarray sum is dp[i] = max(a[i], dp[i-1] + a[i]) (continue the previous subarray or start a new one)

For subset sum, you would do dp[i] = max(a[i], dp[i-1] + a[i]) as well??? im confused. nope its dp[i] = max(dp[i-1], dp[i-1] + a[i], a[i])

• you have 3 choices: the best subset doesn’t have this value, the subset includes this value, and it’s a new subset starting at a[i]

Sum of subarray minimums

https://leetcode.com/problems/sum-of-subarray-minimums/

• https://leetcode.com/problems/sum-of-subarray-minimums/editorial/

Maximum XOR subarray

See XOR. You can calculate it in $O(n)$ with a big time constant.

Increase subarray sum

This is also a pretty interesting problem, ~1400 rated. https://codeforces.com/problemset/problem/1644/C