d*******l
发帖数: 338 | 1 int MaxProduct(int a[], int n)
{
int maxp = 0, maxn = 0;
int ans = 0;
for(int i = 0; i < n; i++) {
if(!a[i]) maxp = maxn = 0;
else if(a[i] > 0) {
maxp = max(maxp*a[i], a[i]);
maxn = a[i]*maxn;
} else {
int t = maxn;
maxn = min(maxp*a[i], a[i]);
maxp = a[i]*t;
}
ans = max(ans, maxp);
}
return (n==1)?a[0]:ans;
} |
|
p********r
发帖数: 66 | 2 这是一道DP的算法题
对长度为n的字符串str, 求maxp(str)
1. 如果str[0] == str[n-1], maxp(str) = 2+maxp(str[1 .. n-2])
2. 如果str[0] != str[n-1], maxp(str) = max(maxp(str[0 .. n-2]), maxp(str[1 .
. n-1]))
3. 循环递归 1， 2
用递归的话算法复杂度是O(2^n)
但是中间有很多运算是重复的，我们定义一个二维数组记录子字符串str[i .. j]的
maxp
算法复杂度变成O(n^2) |
|
s*******f
发帖数: 1114 | 3 int EarnMost(int prices[], int len){
if (!prices !! len < 1)
return 0;
int minp = prices[0];
int maxp = prices[0];
int ret = 0;
for (int i = 1; i < len; ++i){
if (prices[i] > maxp){
maxp = prices[i];
ret = maxp - minp > ret? maxp - minp:ret;
}else if (prices[i] < minp){
minp = prices[i];
maxp = prices[i];
}
}
return ret;
}
if [5,4,3,2,1], it returns 0, not -1. |
|
r********g
发帖数: 1351 | 4 第一题记得是用两个list来记录正的最大值和负的最大值。但是corner case不是很清
楚：
比如：如果只有一个元素，是负数，那返回这个负数，还是返回0呢？（0的意思可以理
解成0个连续元素）。
int maxSubArray(int A[], int n) {
if(n == 0) return 0;
//init
int *minList = new int[n];
int *maxList = new int[n];
memset(minList, 0, sizeof(int)*n);
memset(maxList, 0, sizeof(int)*n);
int maxP = 0;
if(A[0] > 0) {
maxList[0] = A[0];
maxP = A[0];
}
else minList[0] = A[0];
//compute
for(int i = 1; i < n; i++){
if(A[i] == 0)... 阅读全帖 |
|
p*g
发帖数: 141 | 5 int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;
int* front = new int [size];
front[0] = 0;
int minp = prices[0];
for (int i=1; i
int p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}
int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1]... 阅读全帖 |
|
p*g
发帖数: 141 | 6 int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;
int* front = new int [size];
front[0] = 0;
int minp = prices[0];
for (int i=1; i
int p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}
int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1]... 阅读全帖 |
|
p*g
发帖数: 141 | 7 int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;
int* front = new int [size];
front[0] = 0;
int minp = prices[0];
for (int i=1; i
int p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}
int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1]... 阅读全帖 |
|
p*g
发帖数: 141 | 8 int maxProfit(vector &prices) {
int size = prices.size();
if (size<=1)
return 0;
int* front = new int [size];
front[0] = 0;
int minp = prices[0];
for (int i=1; i
int p = prices[i];
front[i] = max(front[i-1], p-minp);
minp = min(minp, p);
}
int* back =new int[size];
back[size-1] = 0;
int maxp = prices[size-1]... 阅读全帖 |
|
s*****y
发帖数: 897 | 9 1.10 Given a two dimensional graph with 6000 points on it, find a line which
passes the most number of points.
Basic Idea: We need two points to define a line. So, for all possible lines,
check which has the max number of points passing though. Let’s say there
are N points, and P is the set of all points.
Algorithm:
Lmax = 0, Maxp=0 for all pairs of point (Pi,Pj) in P
calculate number of points m passing through the line L(P1,Pj) if (m > Maxp)
{
Maxp = m; Lmax = L(Pi,Pj);
} return Lmax;
Time com... 阅读全帖 |
|
z*********o
发帖数: 541 | 10 α: type I error,β: type II error.
α=maxPθ(x1---xn)εC]
1-Pθ[type II error] =Pθ[(x1---xn)εC]=γc(θ)
怎莫理解他们三者之间的关系？α 难道等于power function=Pθ[(x1---xn)εC]=γc(
θ)?
帮忙解释一下。谢谢 |
|
