最大子数组和

问题

求解最大子数组和（Maximum Subarray Sum）：给定一个整数数组，需要找到具有最大和的连续子数组。例如，对于数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组和为[4, -1, 2, 1]，其和为6。

解题步骤

当我们需要求解一个数组中的最大子数组和时，可以使用分治算法来解决。该算法的基本思路是将数组递归地划分为更小的子数组，然后分别求解左右子数组的最大子数组和。最后，还需要考虑跨越中点的最大子数组和。

具体步骤如下：

首先，我们将给定的数组划分为两个较小的子数组，分别为左子数组和右子数组。划分的方法是找到数组的中间位置。
然后，我们递归地求解左子数组和右子数组的最大子数组和。这一步可以通过再次调用分治算法来实现。递归的终止条件是当子数组中只有一个元素时，直接返回该元素。
接下来，我们需要考虑跨越中点的最大子数组和。我们从中点向左扩展，找到左侧的最大子数组和，然后从中点向右扩展，找到右侧的最大子数组和。这一步是通过线性时间的操作来实现的。
最后，我们比较左子数组的最大子数组和、右子数组的最大子数组和以及跨越中点的最大子数组和，取其中的最大值作为最终的最大子数组和。

通过不断地递归和合并子数组，我们可以找到整个数组的最大子数组和。这种分治算法的关键在于将问题划分为更小的子问题，并在合并过程中考虑到可能跨越子数组边界的情况。这样可以大大减少问题的规模，提高算法的效率。

题解

public class MaximumSubarraySum {
    public static int findMaxSubarray(int[] arr) {
        return findMaxSubarray(arr, 0, arr.length - 1);
    }

    private static int findMaxSubarray(int[] arr, int low, int high) {
        if (low == high) {
            return arr[low];
        }

        int mid = (low + high) / 2;

        int leftMaxSum = findMaxSubarray(arr, low, mid);
        int rightMaxSum = findMaxSubarray(arr, mid + 1, high);
        int crossMaxSum = findMaxCrossingSubarray(arr, low, mid, high);

        return Math.max(Math.max(leftMaxSum, rightMaxSum), crossMaxSum);
    }

    private static int findMaxCrossingSubarray(int[] arr, int low, int mid, int high) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            leftSum = Math.max(leftSum, sum);
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = findMaxSubarray(arr);
        System.out.println("Maximum Subarray Sum: " + maxSum);
    }
}

function findMaxSubarray(arr) {
  return findMaxSubarrayHelper(arr, 0, arr.length - 1);
}

function findMaxSubarrayHelper(arr, low, high) {
  if (low === high) {
    return arr[low];
  }

  const mid = Math.floor((low + high) / 2);

  const leftMaxSum = findMaxSubarrayHelper(arr, low, mid);
  const rightMaxSum = findMaxSubarrayHelper(arr, mid + 1, high);
  const crossMaxSum = findMaxCrossingSubarray(arr, low, mid, high);

  return Math.max(leftMaxSum, rightMaxSum, crossMaxSum);
}

function findMaxCrossingSubarray(arr, low, mid, high) {
  let leftSum = Number.NEGATIVE_INFINITY;
  let sum = 0;
  for (let i = mid; i >= low; i--) {
    sum += arr[i];
    leftSum = Math.max(leftSum, sum);
  }

  let rightSum = Number.NEGATIVE_INFINITY;
  sum = 0;
  for (let i = mid + 1; i <= high; i++) {
    sum += arr[i];
    rightSum = Math.max(rightSum, sum);
  }

  return leftSum + rightSum;
}

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSum = findMaxSubarray(arr);
console.log("Maximum Subarray Sum:", maxSum);

def find_max_subarray(arr):
    return find_max_subarray_helper(arr, 0, len(arr) - 1)

def find_max_subarray_helper(arr, low, high):
    if low == high:
        return arr[low]

    mid = (low + high) // 2

    left_max_sum = find_max_subarray_helper(arr, low, mid)
    right_max_sum = find_max_subarray_helper(arr, mid + 1, high)
    cross_max_sum = find_max_crossing_subarray(arr, low, mid, high)

    return max(left_max_sum, right_max_sum, cross_max_sum)

def find_max_crossing_subarray(arr, low, mid, high):
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, low - 1, -1):
        sum += arr[i]
        left_sum = max(left_sum, sum)

    right_sum = float('-inf')
    sum = 0
    for i in range(mid + 1, high + 1):
        sum += arr[i]
        right_sum = max(right_sum, sum)

    return left_sum + right_sum

arr = [-2,```python
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = find_max_subarray(arr)
print("Maximum Subarray Sum:", max_sum)

package main

import "fmt"

func findMaxSubarray(arr []int) int {
	return findMaxSubarrayHelper(arr, 0, len(arr)-1)
}

func findMaxSubarrayHelper(arr []int, low, high int) int {
	if low == high {
		return arr[low]
	}

	mid := (low + high) / 2

	leftMaxSum := findMaxSubarrayHelper(arr, low, mid)
	rightMaxSum := findMaxSubarrayHelper(arr, mid+1, high)
	crossMaxSum := findMaxCrossingSubarray(arr, low, mid, high)

	return max(leftMaxSum, rightMaxSum, crossMaxSum)
}

func findMaxCrossingSubarray(arr []int, low, mid, high int) int {
	leftSum := -1 << 31
	sum := 0
	for i := mid; i >= low; i-- {
		sum += arr[i]
		leftSum = max(leftSum, sum)
	}

	rightSum := -1 << 31
	sum = 0
	for i := mid + 1; i <= high; i++ {
		sum += arr[i]
		rightSum = max(rightSum, sum)
	}

	return leftSum + rightSum
}

func max(a, b, c int) int {
	if a >= b && a >= c {
		return a
	} else if b >= a && b >= c {
		return b
	} else {
		return c
	}
}

func main() {
	arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	maxSum := findMaxSubarray(arr)
	fmt.Println("Maximum Subarray Sum:", maxSum)
}

最大子数组和

# 最大子数组和

# 问题

# 解题步骤

# 题解

最大子数组和

问题

解题步骤

题解