maintain invariance: "max_so_far" and "max_current".
Calculate the max till current number. it only depends if the previous max is "+" or "-";
public class Solution {
public int maxSubArray(int[] nums) {
int max_current = nums[0];
int max_so_far = nums[0];
for(int i=1; i < nums.length; i++) {
max_current = max_current>0? nums[i]+max_current:nums[i];
max_so_far = Math.max(max_so_far, max_current);
}
return max_so_far;
}
}
53. Maximum Subarray Find the contiguous subarray within ...
53. Maximum Subarray Find the contiguous subarray within ...
53. Maximum Subarray Description Given an integer array n...
53. Maximum Subarray Given an integer array nums, find th...
53. Maximum Subarray --- Easy[https://leetcode.com/proble...
Dynamic Programming（动态规划） 53. Maximum Subarray 最大和子数组（元素连...
53.最大子数组和[https://leetcode.cn/problems/maximum-subarray/]...
剑指Offer 42：连续子数组最大和 Leetcode 53. Maximum Subarray 思路比较简单：...
Find the contiguous subarray within an array (containing ...
Problem Given an integer array nums, find the contiguous ...
本文标题：53. Maximum Subarray
本文链接：https://www.haomeiwen.com/subject/hjmamttx.html
网友评论