p53

发表于 | 分类于 |

LeetCode p53 Maximum Subarray 题解

1.题目：

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.

题意：

输入一个数组，计算其子数组最大的和。

2.解题思路:

见代码
牛课网直播看到过2333

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
public class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
		int max = nums[0];
		int sum = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (sum < 0) {
				sum = 0;
			}
			sum = sum + nums[i];
			if (sum > max) {
				max = sum;
			}
		}
		ans = max > sum ? max : sum;
		return ans;
    }
}

4.一些总结：