T*******e
发帖数: 4928 | 1 所以你会用一个变量存着p的子树的最大和值maxSoFar，然后比较p的子树的最大值
maxSoFar与那四个通过p的最大和值maxAcrossCurNode,来更新从下往上走到p为止的最
大值maxSoFar。
int maxPathSumHelper(TreeNode *cur, int &maxSoFar){
if(!cur) return 0;
int maxLeft=maxPathSumHelper(cur->left, maxSoFar);
int maxRight=maxPathSumHelper(cur->right, maxSoFar);
int maxAcrossCurNode=cur->val;
if(maxLeft>0) maxAcrossCurNode+=maxLeft;
if(maxRight>0) maxAcrossCurNode+=maxRight;
maxSoFar=max(maxAcrossCurNode, maxSoFar); //update maxSoFar !!!!
return max(cur->val,... 阅读全帖 |
|
a****x
发帖数: 89 | 2 多谢指教，仿照你的写了个java的，pass了：
private LocalResult maxPathSumLocal(TreeNode root)
{
if(root == null)
{
return new LocalResult(0,0);
}
LocalResult left = maxPathSumLocal(root.left);
LocalResult right = maxPathSumLocal(root.right);
int maxSoFar,leg;
if(root.left == null && root.right == null)
maxSoFar = root.val;
else if(root.left == null)
maxSoFar = maxOfTwo(right.maxSo... 阅读全帖 |
|
s*****o
发帖数: 1540 | 3 一个经典问题：a vector x of n real numbers. find the max sum found in any
contiguous sub vector。
大家知道，programming pearl的解法是：
maxsofar = 0;
maxendinghere = 0;
for i = [0, n)
maxendinghere = max (maxendinghere + x[i], 0);
maxsofar = max (maxsofar, maxendinghere);
我改动一下，要输出究竟是那个sub vector，请大侠指教是不是正确。
public class MaxSubVector {
static public void findBigestSum(double[] x)
{
double maxsofar = 0;
double maxendinghere = 0;
int maxsofarlow = -1;
int maxso... 阅读全帖 |
|
m***n
发帖数: 2154 | 4 public static int rainwater(int[] level) {
int len = level.length;
int [] L = new int[len];
int [] R = new int[len];
int [] water = new int[len];
int maxsofar = 0;
for(int i=0;i
maxsofar = Math.max(level[i],maxsofar);
L[i] = maxsofar;
}
maxsofar =0;
for(int i=len-1;i>=0;i--) {
maxsofar = Math.max(level[i],maxsofar);
R[i] = maxsofar;
}
int sum=0;
... 阅读全帖 |
|
m***n
发帖数: 2154 | 5 public static int rainwater(int[] level) {
int len = level.length;
int [] L = new int[len];
int [] R = new int[len];
int [] water = new int[len];
int maxsofar = 0;
for(int i=0;i
maxsofar = Math.max(level[i],maxsofar);
L[i] = maxsofar;
}
maxsofar =0;
for(int i=len-1;i>=0;i--) {
maxsofar = Math.max(level[i],maxsofar);
R[i] = maxsofar;
}
int sum=0;
... 阅读全帖 |
|
h*****f
发帖数: 248 | 6 #include
struct Node {
int value;
Node* pLeft;
Node* pRight;
};
int findMaxSubTree(Node* pNode, int& maxSoFar) {
if (!pNode) return 0;
int leftSum = findMaxSubTree(pNode->pLeft, maxSoFar);
int rightSum = findMaxSubTree(pNode->pRight, maxSoFar);
int currentSum = pNode->value + std::max(0, leftSum) + std::max(0,
rightSum);
maxSoFar = std::max(currentSum, maxSoFar);
return currentSum;
}
int main() {
Node node4 = {4, NULL, NULL};
Node node3 = {3, NULL, NULL... 阅读全帖 |
|
b*****u
发帖数: 648 | 7 递归，有点tricky的地方在于递归函数每次返回的是最大的单侧路径，但同时把两侧加
自己的和与记录的最大值比较，最终返回的是那个记录值
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int maxSoFar= root->val;
int tmp = maxContainRoot(root, maxSoFar);
return maxSoFar;
}
int maxContainRoot(TreeNode *root, int& maxSoFar)
{
if (root == NULL) return 0;
int leftMax = maxContainRoot(root->left,maxSoFar);
... 阅读全帖 |
|
T******7
发帖数: 1419 | 8 //==========================================================================
==
// Binary Tree Maximum Path Sum
// Given a binary tree, find the maximum path sum.
//
// The path may start and end at any node in the tree.
//
// For example:
// Given the below binary tree,
//
// " 1 "
// " / \ "
// " 2 3 "
//
// Return 6.
//
//==========================================================================
==
#include
using namespace std;
/**
* Definition for binary t... 阅读全帖 |
|
H***e
发帖数: 476 | 9 他给的算法是:
maxsofar = 0;
maxendinghere = 0;
for i = 0: n-1
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
end
这个如果全部都是负数(-5 -1 -2 -4 -3)，算出来的是0，which is not true; 应该是
-1
我觉得应该改下:
maxsofar = -INF;
maxendinghere = -INF;
for i = 0: n-1
maxendinghere = max(maxendinghere + x[i], x[i])
maxsofar = max(maxsofar, maxendinghere)
end
am i missing something?
谢谢 |
|
f****g
发帖数: 313 | 10 I check the book again, and the best algorithm is in O(n), haha
Here is the pseudo code copied from "Programming Pearl"
maxsofar = 0;
maxendinghere = 0;
for i = [0,n)
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
the run time is O(n). It is DP problem.
Let me know if you still have any question about it:S |
|
p**p
发帖数: 742 | 11 我写的java code O(m*m*n) 实现：
本质上跟max sub-matrix sum 差不多，就是把二维问题转化为一维。
public int getSubMatrixWithEqual0And1(int[][] matrix) {
int m, n;
if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].
length) == 0) {
return 0;
}
int overallMax = 0;
for(int i = 0; i < m; i++) {
int[] rowSum = new int[n];
for(int j = i; j < m; j++) {
for(int k = 0; k < n; k++) {
rowSum[k] += matri... 阅读全帖 |
|
t******e
发帖数: 1293 | 12 from <>
int maxsofar = 0;
int maxendinghere = 0;
for (int i = 0; i < n; ++i)
{
maxendinghere = max(maxendinghere + a[i], 0);
maxsofar = max(maxsofar, maxendinghere);
} |
|
l*******r
发帖数: 511 | 13 for i=1 to n
maxendinghere=max(maxendinghere+x_i,0)
maxsofar=max(maxsofar,maxendinghere) |
|
b********g
发帖数: 43 | 14
Newton ?
2: )not continuous
1. maxsofar maxendinghere
2. all positive
dont'know what it means... |
|
S****t
发帖数: 1186 | 15 来自主题: BrainTeaser版 - 两个程序题 (1)
bool SumX(int *a, int n, int x)
{
int i = 0, j = n - 1;
while (i < j)
{
if (a[i] + a[j] > x)
{
j--;
countinue;
}//if
else if (a[i] + a[j] < x)
{
i++;
countinue;
}//else if
else
{
return true;
}//else
}//while
return false;
}//SumX
(2)
int MaxSubArray(int *a, int n)
{
maxSoFar = 0;
maxEndingHere = 0;
for (int i = 0; i < n; i++)
{
maxEndingHere = ((maxEndingHere + a[i]) > 0) ? (maxEndingHere + a[i]) :
0; |
|
