Maintain a local max and global max, update the max with current value (starting a new array) or max + current value (continuous array).
T: O(n) S: O(1)
public int maxSubArray(int[] nums) {
int max = nums[0], curtmax = nums[0];
for (int i = 1; i < nums.length; i++) {
curtmax = Math.max(curtmax + nums[i], nums[i]);
max = Math.max(max, curtmax);
}
return max;
}
Solution 2:
Solution 3: DP
def maxSubArray(self, nums: List[int]) -> int:
dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
maxx = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i - 1] + nums[i], nums[i])
maxx = max(dp[i], maxx)
return maxx
Use prefix sum and store the count of sum in a hashmap. When map.containsKey(sum - k), it indicates that there is a subarray sum which equals k, add it to the result.
Add a record to map (map.put(0, 1)), this give the count between any number 0, in case that number equals k.
T: O(n) S: O(n)
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, result = 0;
for (int n : nums) {
sum += n;
if (map.containsKey(sum - k)) {
result += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return result;
}
Addition to LC560, store the minimum subarray lens before i which sums to target in a min array. When the previous minimum prevMin exists, it means there is a subarray sums to sum - target. That lens is i - prevMin. The result is the current min and previous min, which is i - prevMin + min[prevMin].
public int minSumOfLengths(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
map.put(0, -1);
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
map.put(sum, i);
}
sum = 0;
int one = Integer.MAX_VALUE, res = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - target)) {
one = Math.min(one, i - map.get(sum - target));
}
if (map.containsKey(sum + target) && one != Integer.MAX_VALUE) {
res = Math.min(res, one + (map.get(sum + target) - i));
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
public int minSumOfLengths(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int n = arr.length;
int[] min = new int[n];
Arrays.fill(min, Integer.MAX_VALUE);
int sum = 0;
int best = Integer.MAX_VALUE;
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
sum += arr[i];
Integer prevMin = map.get(sum - target);
if (prevMin != null) {
if (prevMin != -1 && min[prevMin] != Integer.MAX_VALUE) {
res = Math.min(res, i - prevMin + min[prevMin]);
}
best = Math.min(best, i - prevMin);
}
min[i] = best;
map.put(sum, i);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int best[] = new int[n];
Arrays.fill(best, Integer.MAX_VALUE);
int sum = 0, start = 0, ans = Integer.MAX_VALUE, bestSoFar = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
sum += arr[i];
while(sum > target){
sum -= arr[start];
start++;
}
if(sum == target){
if(start > 0 && best[start - 1] != Integer.MAX_VALUE){
ans = min(ans, best[start - 1] + i - start + 1);
}
bestSoFar = min(bestSoFar, i - start + 1);
}
best[i] = bestSoFar;
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (k != 0) sum %= k;
if (map.containsKey(sum)) {
if (map.get(sum) < i - 1) return true;
} else {
map.put(sum, i);
}
}
return false;
}
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0, res = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
res = Math.max(res, i - map.get(sum - k));
}
if (!map.containsKey(sum)) map.put(sum, i);
}
return res;
}
Maintain both positive and negative values in two arrays, update with current min/max.
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
_dict = {}
_dict[0] = -1
_sum = 0
_min = sys.maxsize
for i in range(len(nums)):
_sum += nums[i]
if _sum - k in _dict:
_min = min(_min, i - _dict[_sum - k])
if _sum not in _dict:
_dict[_sum] = i
return 0 if _min == sys.maxsize else _min
public int maxProduct(int[] nums) {
int n = nums.length;
int[] pos = new int[n];
int[] neg = new int[n];
int max = nums[0];
pos[0] = neg[0] = nums[0];
for (int i = 1; i < n; i++) {
pos[i] = Math.max(Math.max(pos[i - 1] * nums[i], neg[i - 1] * nums[i]),
nums[i]);
neg[i] = Math.min(Math.min(pos[i - 1] * nums[i], neg[i - 1] * nums[i]),
nums[i]);
max = Math.max(max, pos[i]);
}
return max;
}
Maintain a prefix product. When encounter 0, reset the prefix product list.
Add: T: O(1), GetProduct: T: O(1)
List<Integer> list;
public ProductOfNumbers() {
list = new ArrayList<>();
list.add(1);
}
public void add(int num) {
if (num > 0) {
list.add(list.get(list.size() - 1) * num);
} else {
list = new ArrayList<>();
list.add(1);
}
}
public int getProduct(int k) {
if (k >= list.size()) return 0;
return list.get(list.size() - 1) / list.get(list.size() - k - 1);
}
List<Integer> list;
TreeMap<Integer, int[]> memo; // start : [end, product]
public ProductOfNumbers() {
list = new ArrayList<>();
memo = new TreeMap<>();
}
public void add(int num) {
list.add(num);
}
public int getProduct(int k) {
int endIndex = list.size() - 1;
int startIndex = endIndex - k + 1;
int product = 1;
if (memo.containsKey(startIndex)) {
int[] temp = memo.get(startIndex);
int newend = temp[0];
product *= temp[1] * getProductBetween(newend + 1, endIndex);
} else if (memo.ceilingKey(startIndex) != null) {
int ceil = memo.ceilingKey(startIndex);
int[] temp = memo.get(ceil);
int newend = temp[0];
product *= getProductBetween(startIndex, ceil - 1) * temp[1] * getProductBetween(newend + 1, endIndex);
} else {
product = getProductBetween(startIndex, endIndex);
}
memo.put(startIndex, new int[]{endIndex, product});
return product;
}
private int getProductBetween(int start, int end) {
int product = 1;
for (int i = start; i <= end; i++) {
product *= list.get(i);
}
return product;
}