This is the solution about Leetcode-Maximum Subarray.

Description

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution

Analysis

Solution1

  1. Try all possible combinations and get the maximum one.
  2. Time complexity is O(n^2)

Solution2

  1. The main point is we store the sum of 0 - i elements for each location in array. Then we only need to check if sum[j] - sum[i] == k, it represents the sum of i+1 to j.
  2. We use HashMap to get the constant time for the check stuff.
  3. Time complexity is O(n+n+n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution1 {
public int maxSubArrayLen(int[] nums, int k) {
int maxLen = 0;
for(int i=0; i<nums.length; i++) {
int sum = nums[i];
if(sum==k) maxLen = Math.max(maxLen,1);
for(int j=i+1; j<nums.length; j++) {
sum += nums[j];
if(sum == k) {
maxLen = Math.max(maxLen,j-i+1);
}
}
}
return maxLen;
}
}
public class Solution2 {
public int maxSubArrayLen(int[] nums, int k) {
int maxLen = 0;
//in order to preprocess the data easier,assign 0 to sum[0]
int[] sum = new int[nums.length+1];
sum[0] = 0;
for(int i=1;i<sum.length; i++) {
sum[i] = sum[i-1] + nums[i-1];
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<sum.length; i++) {
map.put(sum[i],i);
}
for(int i=0;i<sum.length; i++) {
Integer val = map.get(sum[i]+k);
if(val!=null && val.intValue()-i>maxLen) {
maxLen = val.intValue()-i;
}
}
return maxLen;
}
}