MaxSum算法怎么用
时间: 2023-05-21 18:01:35 浏览: 57
MaxSum算法是一种动态规划算法,用于求解序列中的最大子序列和。具体实现方法如下:
1. 定义两个变量:maxSum和curSum,分别表示当前最大子序列和和当前子序列和。
2. 遍历整个序列,对于每个元素,执行以下操作:
a. 如果curSum小于等于0,则将curSum赋值为当前元素的值。
b. 如果curSum大于0,则将curSum加上当前元素的值。
c. 如果curSum大于maxSum,则将maxSum赋值为curSum。
3. 遍历结束后,maxSum即为最大子序列和。
下面是MaxSum算法的Python实现:
def maxSum(nums):
maxSum = float('-inf')
curSum = 0
for num in nums:
if curSum <= 0:
curSum = num
else:
curSum += num
if curSum > maxSum:
maxSum = curSum
return maxSum
print(maxSum([1, -2, 3, 10, -4, 7, 2, -5])) # 输出18,对应子序列[3, 10, -4, 7, 2]
相关问题
使用分治法解决这个问题,用kotlin:var maxSum = nums[0] var currentSum = nums[0] for (i in 1 until nums.size) { currentSum = maxOf(currentSum + nums[i], nums[i]) maxSum = maxOf(maxSum, currentSum) } return maxSum
使用分治法解决最大子序和问题的思路是将数组分成左右两部分,分别计算左边、右边和横跨左右两部分的最大子序和,最终的最大子序和就是这三个值的最大值。
下面是使用 Kotlin 实现的分治法:
```
fun maxSubArray(nums: IntArray): Int {
return maxSubArrayHelper(nums, 0, nums.size - 1)
}
fun maxSubArrayHelper(nums: IntArray, left: Int, right: Int): Int {
if (left == right) {
return nums[left]
}
val mid = (left + right) / 2
val leftMaxSum = maxSubArrayHelper(nums, left, mid)
val rightMaxSum = maxSubArrayHelper(nums, mid + 1, right)
var leftCrossMaxSum = Int.MIN_VALUE
var leftCrossSum = 0
for (i in mid downTo left) {
leftCrossSum += nums[i]
leftCrossMaxSum = maxOf(leftCrossMaxSum, leftCrossSum)
}
var rightCrossMaxSum = Int.MIN_VALUE
var rightCrossSum = 0
for (i in mid + 1..right) {
rightCrossSum += nums[i]
rightCrossMaxSum = maxOf(rightCrossMaxSum, rightCrossSum)
}
return maxOf(leftMaxSum, rightMaxSum, leftCrossMaxSum + rightCrossMaxSum)
}
```
在 `maxSubArray` 函数中,我们调用 `maxSubArrayHelper` 来计算最大子序和。在 `maxSubArrayHelper` 中,我们首先处理递归结束的情况,即 left == right,此时最大子序和就是 nums[left]。
然后,我们计算左半部分的最大子序和 `leftMaxSum` 和右半部分的最大子序和 `rightMaxSum`。接着,我们计算横跨左右两部分的最大子序和 `leftCrossMaxSum + rightCrossMaxSum`,其中 `leftCrossMaxSum` 表示左半部分的跨越中包含最后一个元素的最大子序和,`rightCrossMaxSum` 表示右半部分的跨越中包含第一个元素的最大子序和。
最后,我们返回 `leftMaxSum`、`rightMaxSum` 和 `leftCrossMaxSum + rightCrossMaxSum` 中的最大值即可。
这个算法的时间复杂度是 O(nlogn),空间复杂度是 O(logn)。
求结点到叶子节点的路径上所有值之和的最大值int Maxsum(struct TreeNode* root){ if(root==NULL){ return 0; } return root->val+max(Maxsum(root->left),Maxsum(root->right)); }
这个函数实现的是求二叉树中从根节点到叶子节点的路径上所有值之和的最大值。这个算法的思路是:
- 如果当前节点为空,则返回0
- 如果当前节点是叶子节点,则返回节点的值
- 如果当前节点不是叶子节点,则递归求其左右子树的最大路径和,然后加上当前节点的值,返回结果
完整的代码如下:
```
int Maxsum(struct TreeNode* root){
if(root==NULL){
return 0;
}
if(root->left==NULL && root->right==NULL){
return root->val;
}
int leftMax = Maxsum(root->left);
int rightMax = Maxsum(root->right);
return root->val + max(leftMax, rightMax);
}
```
需要注意的是,在递归过程中,我们需要判断当前节点是否为叶子节点,因为只有叶子节点才能作为路径的终点。