0053.最大子数组和

https://leetcode.cn/problems/maximum-subarray

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func maxSubArray(nums []int) int {
	ans := nums[0]
	for sum, i := 0, 0; i < len(nums); i++ {
		sum += nums[i]
		if sum > ans {
			ans = sum
		}
		if sum < 0 {
			sum = 0
		}
	}
	return ans
}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut ans = nums[0];
        let mut sum = 0;
        for v in nums {
            sum += v;
            if sum > ans {
                ans = sum;
            }
            if sum < 0 {
                sum = 0;
            }
        }
        ans
    }
}