求解最大子数组的和

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

Example:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

初看这道题，好像很简单（照LeetCode的难度系数来看好像的确是挺简单的哈哈），然而在牛客网提交的代码通过了，在LeetCode这里却没有通过，好严格。。。

一般来说，这种题目其实都可以无脑用暴力解法的，虽然效率极低，有时候甚至会超时，但是确实也是一种思路。

class Solution {
    public int maxSubArray(int[] nums) {
       int length = nums.length;
        int result = nums[0];
        int sum;
        for(int i = 0; i < length; i++)
        {
            sum = 0;
            for(int j = i; j < length; j++)
            {
                sum += nums[j];
                if(sum > result)
                {
                    result = sum;
                }
            }
        }

        return result;
    }
}

　　用sum保存子序列的和，result储存暂时的结果。这个结果是可行的，不过效率太低了，执行用时102ms，可能序列再长一点就超时了。

　  白天在网上看到了一个巧妙的解法，借鉴了一下，然后编写出来，效率飞涨。

class Solution {
    public int maxSubArray(int[] nums) {
       int length = nums.length;
        int result = nums[0];
        int temp = 0;
        for(int i = 0; i < length; i++)
        {
            temp += nums[i];
            if(temp > result)
            {
                result = temp;
            }
            if(temp < 0)
            {
                temp = 0;
            }
        }

        return result;
    }
}