LC：最大子数组和

题目：给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

方法一： 暴力法

1. 取 i，j 用于标记位。i 用于记录从哪个位置开始连续，j 用于进行连续。如：

[0,1,2,3,4]     i 指向0

j 指向0：0

j 指向1：0,1

j 指向2：0,1,2

j 指向3：0,1,2,3

j 指向4：0,1,2,3,4

2. 取最大值max（初始值设为最小），sum为和值。sum用于计算从 i 到 j 位置中的所有数之和，并与max进行比较，如果大于max，则将sum值赋予max。

3. 遍历数组，直到 i 值为数组中最后一位，计算出sum值，并与max值进行比较。 

4. 返回max值。

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define InitSize 20
typedef int ElemType;
typedef struct{
	ElemType *data;
	int length;
}SqList;

// 初始化顺序表
void initSqList(SqList &L){
	ElemType x;
	L.length = 0;
	L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
	printf("请输入顺序表（9999为终止）：");
	scanf("%d",&x);
	while(x!=9999){
		L.data[L.length]=x;
		L.length++;
		scanf("%d",&x);
	}
}

// 打印顺序表
void printSqList(SqList L){
	for(int i=0;i<L.length;++i)
		printf("%d ",L.data[i]);
	printf("\n");
}

// 最大子数组和
ElemType maxSubArray(SqList L){
	ElemType max = INT_MIN; //INT_MIN需要引入limits.h头文件
	ElemType sum;
	for(int i=0;i<L.length;i++){
		sum = 0;
		for(int j=i;j<L.length;j++){
			sum+=L.data[j];
			if(max<sum) 
				max=sum;
		}
	}
	return max;
}

void main(){
	ElemType res;
	SqList L;
	initSqList(L);
	printSqList(L);
	res = maxSubArray(L);
	printf("最大和为：%d\n",res);
}

示例1： 

子数组：[5,4,-1,7,8] 

示例2：

子数组：[4,-1,2,1] 

方法二：动态规划

思想：每一步都是在预设之后的最大值

1. 设置result为最终结果值；

2. 每一步，可以和前面合并，也可以不和前面合并，值放入dp数组中。

3. 式子：

dp[i] = max {dp[i-1] +nums[i] , nums[i]}

result = max {dp[i] , result}

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define InitSize 20
typedef int ElemType;
typedef struct{
	ElemType *data;
	int length;
}SqList;

// 初始化顺序表
void initSqList(SqList &L){
	ElemType x;
	L.length = 0;
	L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
	printf("请输入顺序表（9999为终止）：");
	scanf("%d",&x);
	while(x!=9999){
		L.data[L.length]=x;
		L.length++;
		scanf("%d",&x);
	}
}

// 打印顺序表
void printSqList(SqList L){
	for(int i=0;i<L.length;++i)
		printf("%d ",L.data[i]);
	printf("\n");
}

//求最大值
ElemType getMax(ElemType a,ElemType b){
	return a>b?a:b;
}

// 最大子数组和
ElemType maxSubArray(SqList L){
	ElemType dp[InitSize];
	ElemType result;
	dp[0] = L.data[0];
	result = L.data[0];
	for(int i=1;i<L.length;i++){
		dp[i]=getMax(L.data[i],dp[i-1]+L.data[i]);
		result=getMax(dp[i],result);
	}	
	return result;
}

void main(){
	ElemType res;
	SqList L;
	initSqList(L);
	printSqList(L);
	res = maxSubArray(L);
	printf("最大和为：%d\n",res);
}

示例同方法一