C#LeetCode刷题之#53-最大子序和(Maximum Subarray)

C#LeetCode刷题之#53-最大子序和(Maximum Subarray)

问题

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

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.

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };

        var res = maxSubArray(nums);
        Console.WriteLine(res);

        nums = new int[] { 4, 1, 0, -3, -1, 9, 1 };

        res = maxSubArray2(nums);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int maxSubArray(int[] nums) {
        //常规写法
        //记录最大和、本次可以“接受”的和(本次和)
        var max = int.MinValue;
        var thisSum = 0;
        for(var i = 0; i < nums.Length; i++) {
            //如果和小于等于0,那么当前值没有用,应当舍去
            //(为了优化写法,其实是上一次循环时的和)
            //即重置本次和为当前值
            if(thisSum <= 0) {
                thisSum = nums[i];
            } else {
                //否则,迭加和
                thisSum += nums[i];
            }
            //用max记录更大的值
            if(max < thisSum) {
                max = thisSum;
            }
        }
        //返回最大值
        return max;
    }

    private static int maxSubArray2(int[] nums) {
        //高度精简优化写法
        var max = int.MinValue;
        var thisSum = 0;
        for(var i = 0; i < nums.Length; i++) {
            max = Math.Max(max, thisSum = Math.Max(nums[i], thisSum + nums[i]));
        }
        return max;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

6
11

分析:

显而易见,以上2种算法的时间复杂度均为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4012

发表评论

登录后才能评论