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.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [0] Output: 0
Example 4:
Input: nums = [-1] Output: -1
Example 5:
Input: nums = [-100000] Output: -100000
Constraints:
1 <= nums.length <= 3 * 104-105 <= nums[i] <= 105
Follow up: If you have figured out the
O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.Rust Solution
struct Solution;
impl Solution {
fn max_sub_array(nums: Vec<i32>) -> i32 {
let mut prev = 0;
let mut max = std::i32::MIN;
let n = nums.len();
for i in 0..n {
prev = nums[i].max(prev + nums[i]);
max = max.max(prev);
}
max
}
}
#[test]
fn test() {
let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
assert_eq!(Solution::max_sub_array(nums), 6);
let nums = vec![-1];
assert_eq!(Solution::max_sub_array(nums), -1);
let nums = vec![1];
assert_eq!(Solution::max_sub_array(nums), 1);
}
Having problems with this solution? Click here to submit an issue on github.