// 1.cpp : 定义控制台应用程序的入口点。
//
#include
"stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <limits.h>
typedef struct pair
{
int*
C;
int*
B;
int max;
}pair;
//最大连续子数组的和
pair sum(
int* A,
int n)
{
int* B = (
int*)malloc(
sizeof(
int)*(n+
1));
//标志
int* C = (
int*)malloc(
sizeof(
int)*(n+
1));
//C中存放的是每个子问题的最优解
int max = -
INT_MAX;
int i,j;
C[0] =
0;
for(i=
1;i<=n;i++
)
{
if(C[i-
1]+A[i-
1] >= A[i-
1])
{
C[i] = C[i-
1] + A[i-
1];
B[i] =
1;
}
else
{
C[i] = A[i-
1];
B[i] =
0;
}
if(C[i] >
max)
max =
C[i];
}
pair p =
{C,B,max};
return p;
}
//打印出和最大的连续子数组
void print(pair p,
int* A,
int n)
{
int i =
0, j =
0;
for(i=
1;i<=n;i++
)
{
if(p.C[i] ==
p.max)
j =
i;
}
for(i=j;i>=
1 && p.B[i] ==
1;i--
)
{
printf("%d ",A[i-
1]);
}
if(p.B[i] ==
0)
printf("%d ",A[i-
1]);
}
int main()
{
int A[] = {-
1,
0,-
2,
2,
3,
6,
7,-
8};
pair p = sum(A,
8);
printf("连续子数组的最大和为：%d \n",p.max);
printf("和最大的连续子数组为:\n");
print(p,A,8);
return 0;
}
转载于:https://www.cnblogs.com/welsh-android-learning/p/3497518.html
相关资源：C语言求连续最大子数组和的方法
