53. Maximum Subarray (Easy)
https://leetcode.com/problems/maximum-subarray/
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.
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.
Solutions
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
// 'sum' is the summation of prior values if sum > 0
// take it as a single element
int sum = 0;
for (int i = 0; i < nums.length; i++) {
// sum < 0, prior elements are useless since they exert an adverse impact on max summation
if (sum < 0) {
sum = 0;
}
sum += nums[i];
// set the max to sum, max is a global variable, by contrast, sum is a contextual variable
// which is concerning elements prior to current element
if (sum > max) {
max = sum;
}
}
return max;
}
}