最大连续子数组：
暴力求解最大连续子数组
代码：
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int A[8] = { -6, 10, -5, -3, -7, -1, -1 };
int array_length = sizeof(A) / sizeof(A[0]);//数组大小
int sum = -10000;//记录子数组的和
int low;//记录子数组的底
int height;//记录子数组的高
for (int i = 0; i < array_length; i++)
{
for (int j = i ; j < array_length; j++)
{
int subarraysum=0;//所遍历出来的子数组的和
//计算遍历的子数组之和
for (int k = i; k <= j; k++)
{
subarraysum += A[k];
}
//找出最大的子数组
if (subarraysum>sum)
{
sum = subarraysum;
low = i;
height = j;
}
}
}
printf("%d %d %d\n", low, height,sum);//将结果打印出来
getchar();
return 0;
}
2.分治法(算法导论)
代码：
#include <limits.h>
#include <stdio.h>
struct PSum{
int low;
int high;
int sum;
};
//跨越中点的最大子数组,这是最特殊也是最好的找的一段区间
PSum FIND_MAX_CROSSING_SUBARRAY(int *A ,int low , int mid , int high)
{
int i;
int sum=0;
int right_sum=INT_MIN,left_sum=INT_MIN;
int max_left=0,max_right=0;
//先找左边最大的，再找右边最大的，直接暴力找就好了
for(i=mid ; i>=low ; i--){
sum+=A[i];
if(sum>left_sum){
left_sum=sum;
max_left=i;
}
}
sum=0;
for(i=mid+1 ; i<=high ; i++){
sum+=A[i];
if(sum>right_sum){
right_sum=sum;
max_right=i;
}
}
PSum ps;
ps.low = max_left;
ps.high= max_right;
ps.sum = left_sum + right_sum;
return ps;
}
//还是递归的思想，全部都交给中间段来找，如何进行比较大小
PSum FIND_MAXIMUM_SUBARRAY(int *A , int low, int high)
{
if (low == high)
{
PSum ps;
ps.low = low;
ps.high = high;
ps.sum = A[low];
return ps;
}
else{
int mid = (low + high) / 2;
PSum left = FIND_MAXIMUM_SUBARRAY(A, low, mid);
PSum right = FIND_MAXIMUM_SUBARRAY(A, mid + 1, high);
PSum cross = FIND_MAX_CROSSING_SUBARRAY(A, low, mid, high);
if (left.sum >= cross.sum && left.sum >= right.sum){
return left;
}
else if (right.sum >= left.sum && right.sum >= cross.sum){
return right;
}else{
return cross;
}
}
}
int main()
{
int A[8] = {-6, 10, -5, -3, -7, -1, -1};
PSum result;
result = FIND_MAXIMUM_SUBARRAY(A, 0, 7);
printf("%d %d %d\n", result.low , result.high , result.sum);//将结果打印出来
//getchar();
return 0;
}
3.在线算法
代码：
//在线法求最大子数组和问题
int main()
{
int A[8] = { -6, 10, -5, -3, -7, -1, -1 };
int array_length = sizeof(A) /sizeof(A[0]);//数组大小
int sum = 0;//记录子数组的和
int thisSum = 0;
for (int i = 0; i < array_length; i++)
{
thisSum += A[i];
if (thisSum > sum){
sum = thisSum;
}
//如果累加和出现小于0的情况，
//则和最大的子序列肯定不可能包含前面的元素，
//这时将累加和置0，从下个元素重新开始累加
else if (thisSum < 0) {
thisSum = 0;
}
}
printf("%d",sum);//将结果打印出来
return 0;
}
