Maximum Subarray

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

Maybe I just really don’t understand what dynamic programming is.

class Solution {
    public int maxSubArray(int[] nums) {
        var curr = 0;
        var max = Integer.MIN_VALUE;

        for (var i : nums) {
            curr += i;
            max = Math.max(curr, max);
            if (curr < 0) {
                curr = 0;
            }
        }

        return max;
    }
}

Recent posts from blogs that I like

Watching o3 guess a photo's location is surreal, dystopian and wildly entertaining

via Simon Willison

Pre-Raphaelite landscapes of John Brett: 1 Travels

A relatively latecomer, he started painting Pre-Raphaelite landscapes in 1856, with stunning results in the Alps, and his monumental view of Florence, but those proved unsuccessful.

via The Eclectic Light Company

Sometimes the reason you can’t find people you resonate with is because you misread the ones you meet

Sometimes two people will stand next to each other for fifteen years, both feeling out of place and alone, like no one gets them, and then one day, they look up at each other and say, “Oh, there you are.”

via Henrik Karlsson