Maximum Product Subarray
Given an integer array nums, find a subarray that has the largest product, and return the product.
class Solution {
public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = max; // store the max because before updating min your max will already be updated
max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
if (max > ans) {
ans = max;
}
}
return ans;
}
}Related Problems
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.