首页 > 代码库 > 【leetcode】 Unique Binary Search Trees (middle)☆
【leetcode】 Unique Binary Search Trees (middle)☆
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
找数字连续最大乘积子序列。
思路：这个麻烦在有负数和0，我的方法，如果有0，一切都设为初始值。
对于两个0之间的数若有奇数个负数，那则有两种情况，第一种是不要第一个负数和之前的值，第二种是不要最后一个负数和之后的值，用negtiveFront和negtiveBack表示。没有负数就是不要第一个负数和之前的值的情况。
int maxProduct(int A[], int n) { if(n == 0) return 0; int MaxAns = A[0]; int negtiveFront = (A[0] == 0) ? 1 : A[0]; int negtiveBack = (A[0] < 0) ? 1 : 0; for(int i = 1; i < n; i++) { if(A[i] == 0) { MaxAns = (MaxAns > 0) ? MaxAns : 0; negtiveFront = 1; negtiveBack = 0; } else if(A[i] < 0) { negtiveFront *= A[i]; MaxAns = max(negtiveFront, MaxAns); if(negtiveBack == 0) { negtiveBack = 1; } else { negtiveBack *= A[i]; MaxAns = max(negtiveBack, MaxAns); } } else { negtiveFront *= A[i]; negtiveBack *= A[i]; MaxAns = max(negtiveFront, MaxAns); if(negtiveBack > 0) { MaxAns = max(negtiveBack, MaxAns); } } } return MaxAns; }
答案的思路：同时维护包括当前数字A[k]的最大值f(k)和最小值g(k)
f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
再用一个变量Ans存储所有f(k)中最大的数字就可以了
int maxProduct2(int A[], int n) { if(n == 0) return 0; int MaxAns = A[0]; //包括当前A【i】的连续最大乘积 int MinAns = A[0]; //包括当前A【i】的连续最小乘积 int MaxSoFar = A[0]; //整个数组的最大乘积 for(int i = 1; i < n; i++) { int MaxAnsTmp = MaxAns; int MinAnsTmp = MinAns; MaxAns = max(MaxAnsTmp * A[i], max(MinAnsTmp * A[i], A[i])); MinAns = min(MinAnsTmp * A[i], min(MaxAnsTmp * A[i], A[i])); MaxSoFar = max(MaxSoFar, MaxAns); } return MaxSoFar; }
【leetcode】 Unique Binary Search Trees (middle)☆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。