# Maximum Subarray

ID: 35; easy

## Solution 1 (Go)

``````func maxSubArray(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
max, result := nums[0], 0
for i := 0; i < len(nums); i++ {
result += nums[i]
// only update result when it can be increased
if result > max {
max = result
}
if result < 0 {
result = 0
}
}
return max
}``````

## Solution 2 (Go)

``````func Max(x, y int) int {
if x < y {
return y
}
return x
}

func maxSubArray(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
dp, result := make([]int, len(nums)), nums[0]
// base case
dp[0] = nums[0]
// recursive relation
for i := 1; i < len(nums); i++ {
dp[i] = Max(dp[i-1] + nums[i], nums[i])
result = Max(result, dp[i])
}
return result
}``````

## Solution 3 (Java)

``````class Solution {
public int maxSubArray(int[] nums) {
int currSum = nums[0];
int maxSum = nums[0];

for (int i = 1; i < nums.length; i++) {
// if currSum is reset to nums[i], it means that we start at nums[i] now
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
}``````

Last updated