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;
}
