您现在的位置是：首页 > 文章详情

【算法导论】最大子数组——暴力求解

日期：2018-09-02点击：568收藏

1. 暴力方法求解最大子数组问题：求出所有子数组的和并比较；

2. 伪代码

FIND-MAXIMUM-SUBARRAY(A) max = -∞ for i = 1 to A.length sum = 0 for j = i to A.length sum += A[j] if sum > max max = sum low = i high = j return (low, high, max)

3. 代码实现

java

public class MaxArray { private static class Result { int low; int high; int sum; public Result(int low, int high, int sum) { this.low = low; this.high = high; this.sum = sum; } } static Result findMaximumSubarray(int[] A){ int max = Integer.MIN_VALUE; int low = 0; int high = 0; for (int i = 0; i < A.length; i++) { int sum = 0; for (int j = i; j < A.length; j++) { sum += A[j]; if (sum > max) { max = sum; low = i; high = j; } } } return new Result(low, high, max); } }

python

之前用切片其实也是暴力求解

def find_maximum_subarray1(nums): max_sum = -float('inf') result = {} for i in range(len(nums)): total = 0 for j in range(i, len(nums)): print(j) total += nums[j] if total > max_sum: max_sum = total result["low"] = i result["high"] = j result["sum"] = max_sum return result

C语言

typedef struct { int low; int high; int sum; } result; result find_maximum_subarray(int arr[], int len) { int max = -((unsigned)(~0) >> 1); int low, high, i, j; for (i = 0; i < len; i++) { int sum = 0; for(j = i; j < len; j++) { sum += arr[j]; if (sum > max) { max = sum; low = i; high = j; } } } result re; re.low = low; re.high = high; re.sum = max; return re; }