Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Constraints:
1 <= nums.length <= 3 * 104105 <= nums[i] <= 105Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
복잡하게 푸는 방법밖에 생각이 나질 않아 디스커션 보드를 봤다.
배열의 첫 원소부터 더해나가다가 지금까지의 합보다 새로운 원소 값이 더 클 때 max 값을 바꿔준다. 그리고 그 값과 총 맥스 값을 비교한다.
class Solution {
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0], maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}