Leetcode 题目解析之 Maximum Subarray

原创

ruochen

发布于 2022-02-16 21:30:14

1.3K0

发布于 2022-02-16 21:30:14

文章被收录于专栏：若尘的技术专栏若尘的技术专栏

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array −2,1,−3,4,−1,2,1,−5,4,

the contiguous subarray 4,−1,2,1 has the largest sum = 6.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curSum = Math.max(curSum + nums[i], nums[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

coding