Jerry's Notes

Kadane's Algorithm

Dynamic Programming
Word count: 123Reading time: 1 min
2022/01/13

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Kanade’s Algorithm

In an arbitary position i, the maximum subarray sum equals nums[i] or previous maximum subarray sum + nums[i]. This is a Mathematical Induction (MI) problem. Traversal the array nums, we can find the maximum subarray sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int maxSum = nums[0];
        int preSum = nums[0];
        for (int i = 1; i < n; i++) {
            preSum = max(preSum + nums[i], nums[i]);
            maxSum = max(maxSum, preSum);
        }
        return maxSum;
    }
};
Total : 15
2022
Sliding Window BST Dynamic Programming Research Project DFS Permutations Binary Tree Sort BFS love-letter
LeetCode Algorithms for Sensor-Based Robotics Rambling Digression