53. Maximum Subarray Medium

1/**
2 * [53] Maximum Subarray
3 *
4 * Given an integer array nums, find the contiguous subarray (containing at least one number)
5 * which has the largest sum and return its sum.
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
10 * Output: 6
11 * Explanation: [4,-1,2,1] has the largest sum = 6.
12 * 
13 * Example 2:
14 * 
15 * Input: nums = [1]
16 * Output: 1
17 * 
18 * Example 3:
19 * 
20 * Input: nums = [5,4,-1,7,8]
21 * Output: 23
22 * 
23 *  
24 * Constraints:
25 * 
26 * 1 <= nums.length <= 3 * 10^4
27 * -10^5 <= nums[i] <= 10^5
28 * 
29 *  
30 * Follow up: If you have figured out the O(n) solution, try coding another solution using
31 * the divide and conquer approach, which is more subtle.
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/maximum-subarray/
36// discuss: https://leetcode.com/problems/maximum-subarray/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
42        let mut max = nums[0];
43        let mut current = 0;
44        for num in nums {
45            current += num;
46            if current > max {
47                max = current;
48            }
49
50            if current < 0 {
51                current = 0;
52            }
53        }
54        max
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_53() {
66        assert_eq!(Solution::max_sub_array(vec![-2,1,-3,4,-1,2,1,-5,4]), 6);
67    }
68}
69