Skip to content

Prefix Sum Basics

Table of Contents

303. Range Sum Query - Immutable

from typing import List


# Prefix Sum
class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        self.ps = [0 for _ in range(n + 1)]  # prefix sum
        for i in range(1, n + 1):
            self.ps[i] = self.ps[i - 1] + nums[i - 1]

    def sumRange(self, left: int, right: int) -> int:
        return self.ps[right + 1] - self.ps[left]


nums = [-2, 0, 3, -5, 2, -1]
obj = NumArray(nums)
assert obj.sumRange(0, 2) == 1
assert obj.sumRange(2, 5) == -1
assert obj.sumRange(0, 5) == -3
print("PASSED")

3427. Sum of Variable Length Subarrays

2559. Count Vowel Strings in Ranges

3152. Special Array II

1749. Maximum Absolute Sum of Any Subarray

2389. Longest Subsequence With Limited Sum

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Greedy, Sorting, Prefix Sum

3361. Shift Distance Between Two Strings

2055. Plates Between Candles

1744. Can You Eat Your Favorite Candy on Your Favorite Day?

53. Maximum Subarray

  • LeetCode | 力扣

  • Tags: Array, Divide And Conquer, Dynamic Programming

from typing import List


# DP Kadane
def maxSubArrayDP(nums: List[int]) -> int:
    dp = [0 for _ in range(len(nums))]

    dp[0] = nums[0]
    maxSum = nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(
            dp[i - 1] + nums[i],  # continue the previous subarray
            nums[i],  # start a new subarray
        )
        maxSum = max(maxSum, dp[i])

    return maxSum


# Greedy
def maxSubArrayGreedy(nums: List[int]) -> int:
    max_sum = nums[0]
    cur_sum = 0

    for num in nums:
        cur_sum = max(cur_sum + num, num)
        max_sum = max(max_sum, cur_sum)

    return max_sum


# Prefix Sum
def maxSubArrayPrefixSum(nums: List[int]) -> int:
    prefix_sum = 0
    prefix_sum_min = 0
    res = float("-inf")

    for num in nums:
        prefix_sum += num
        res = max(res, prefix_sum - prefix_sum_min)
        prefix_sum_min = min(prefix_sum_min, prefix_sum)

    return res


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArrayDP(nums))  # 6
print(maxSubArrayGreedy(nums))  # 6
print(maxSubArrayPrefixSum(nums))  # 6

1523. Count Odd Numbers in an Interval Range