//grind75
← Back

Kadane's Algorithm (Maximum Subarray)

The classic intro to DP: the largest-sum contiguous subarray in one pass.

1 / 1
func maxSubArray(nums []int) int {

}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])
    }
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
    }
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
        best = max(best, cur)
    }
}
func maxSubArray(nums []int) int {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    best, cur := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur+nums[i])

        // Track the best window we've ever closed off.
        best = max(best, cur)
    }

    return best // O(n) time, O(1) space
}
def max_sub_array(nums):
    pass
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    pass
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]

        # Key choice: extend the previous subarray, or start fresh at nums[i].
        # Starting fresh wins whenever the running sum has gone negative.
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]

    for i in range(1, len(nums)):
        # Key choice: extend the previous subarray, or start fresh at nums[i].
        # Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur + nums[i])
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]

    for i in range(1, len(nums)):
        # Key choice: extend the previous subarray, or start fresh at nums[i].
        # Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur + nums[i])

        # Track the best window we've ever closed off.
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]

    for i in range(1, len(nums)):
        # Key choice: extend the previous subarray, or start fresh at nums[i].
        # Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur + nums[i])

        # Track the best window we've ever closed off.
        best = max(best, cur)
def max_sub_array(nums):
    # best  = best subarray sum seen anywhere.
    # cur   = best subarray sum ending exactly at the current index.
    best, cur = nums[0], nums[0]

    for i in range(1, len(nums)):
        # Key choice: extend the previous subarray, or start fresh at nums[i].
        # Starting fresh wins whenever the running sum has gone negative.
        cur = max(nums[i], cur + nums[i])

        # Track the best window we've ever closed off.
        best = max(best, cur)

    return best  # O(n) time, O(1) space
function maxSubArray(nums) {

}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);
  }
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
  }
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
    best = Math.max(best, cur);
  }
}
function maxSubArray(nums) {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
    best = Math.max(best, cur);
  }

  return best; // O(n) time, O(1) space
}
function maxSubArray(nums: number[]): number {

}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);
  }
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
  }
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
    best = Math.max(best, cur);
  }
}
function maxSubArray(nums: number[]): number {
  // best  = best subarray sum seen anywhere.
  // cur   = best subarray sum ending exactly at the current index.
  let best = nums[0], cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Key choice: extend the previous subarray, or start fresh at nums[i].
    // Starting fresh wins whenever the running sum has gone negative.
    cur = Math.max(nums[i], cur + nums[i]);

    // Track the best window we've ever closed off.
    best = Math.max(best, cur);
  }

  return best; // O(n) time, O(1) space
}
class Solution {
    public int maxSubArray(int[] nums) {

    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.max(nums[i], cur + nums[i]);
        }
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
        }
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = Math.max(best, cur);
        }
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = Math.max(best, cur);
        }

        return best; // O(n) time, O(1) space
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {

    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.Max(nums[i], cur + nums[i]);
        }
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.Max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
        }
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.Max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = Math.Max(best, cur);
        }
    }
}
using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = Math.Max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = Math.Max(best, cur);
        }

        return best; // O(n) time, O(1) space
    }
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {

}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];

        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];

    for (int i = 1; i < numsSize; i++) {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = maxInt(nums[i], cur + nums[i]);
    }
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];

    for (int i = 1; i < numsSize; i++) {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = maxInt(nums[i], cur + nums[i]);

        // Track the best window we've ever closed off.
    }
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];

    for (int i = 1; i < numsSize; i++) {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = maxInt(nums[i], cur + nums[i]);

        // Track the best window we've ever closed off.
        best = maxInt(best, cur);
    }
}
// C has no max for ints, so a tiny helper keeps the two updates readable.
static int maxInt(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize) {
    // best  = best subarray sum seen anywhere.
    // cur   = best subarray sum ending exactly at the current index.
    int best = nums[0], cur = nums[0];

    for (int i = 1; i < numsSize; i++) {
        // Key choice: extend the previous subarray, or start fresh at nums[i].
        // Starting fresh wins whenever the running sum has gone negative.
        cur = maxInt(nums[i], cur + nums[i]);

        // Track the best window we've ever closed off.
        best = maxInt(best, cur);
    }

    return best; // O(n) time, O(1) space
}
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < (int)nums.size(); i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = max(nums[i], cur + nums[i]);
        }
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < (int)nums.size(); i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
        }
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < (int)nums.size(); i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = max(best, cur);
        }
    }
};
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // best  = best subarray sum seen anywhere.
        // cur   = best subarray sum ending exactly at the current index.
        int best = nums[0], cur = nums[0];

        for (int i = 1; i < (int)nums.size(); i++) {
            // Key choice: extend the previous subarray, or start fresh at nums[i].
            // Starting fresh wins whenever the running sum has gone negative.
            cur = max(nums[i], cur + nums[i]);

            // Track the best window we've ever closed off.
            best = max(best, cur);
        }

        return best; // O(n) time, O(1) space
    }
};

Tap the left half to go back, the right half to go forward.

Arrow keys or space to navigate · Esc to exit.