w****x
发帖数: 2483 | 1
//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;
int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
} |
|
w****x
发帖数: 2483 | 2
//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;
int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
} |
|
w****x
发帖数: 2483 | 3 后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
... 阅读全帖 |
|
