🐟 Blog

Maximum Subarray

March 21, 2021


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


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


public int maxSubArray(int[] nums) {
  int globalMax = nums[0];
  int currentMax = nums[0];

  for (int i = 1; i < nums.length; i++) {
    currentMax = Math.max(currentMax + nums[i], nums[i]);    globalMax = Math.max(globalMax, currentMax);

  return globalMax;

State transition

Try clicking on a cell to see how the value is calculated.


To understand the state transition function, it’s important to realize that for dp[i], we’re only concerned with contiguous subarrays that end in that position. It effectively compares the subarrays in a similar way to the O(n2)O(n^2) brute-force approach.


© Attribution Required | 转载请注明原作者与本站链接
© 2022 yujinyan.me