大疆嵌入式8.16 第一道编程题
参考了这位老哥的代码，优化了一下。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <limits.h>
int max(int a,int b)
{
return a>b?a:b;
}
//用两个dp数组，一个正方向，一个逆方向，并把每个下标对应的最大子序和存储在对应的maxNum数组中
int solve(int* data,int N)
{
int dp[N];
int Inv_dp[N];
dp[0]=data[0];
int maxNum[N];
int Inv_maxNum[N];
maxNum[0]=data[0];
//dp[i]：以第 i 个数结尾的「连续子数组的最大和」
//maxNum[i]：前i个数的最大子序和
for(int i=1;i<N;i++)
{
dp[i]=max(dp[i-1]+data[i],data[i]);
maxNum[i]=max(dp[i],maxNum[i-1]);
}
//Inv_dp[i]:逆序，倒着看，以第i个数为结尾的最大和，
//Inv_maxNum[i]:逆序的最大子序和
Inv_dp[N-1]=data[N-1];
Inv_maxNum[N-1]=data[N-1];
for(int i=N-2;i>=0;i--)
{
Inv_dp[i]=max(Inv_dp[i+1]+data[i],data[i]);
Inv_maxNum[i]=max(Inv_dp[i],Inv_maxNum[i+1]);
}
int res=INT_MIN;
//求出最大值
for(int i=1;i<=N-1;i++)
{
int left=maxNum[i-1];
int right=Inv_maxNum[i];
res=max(res,left+right);
}
return res;
}
int main()
{
int data[10]={-1 ,-1 ,-1 ,-1 ,-1, -1, -1, -1 ,-1 ,-1};
//int data[5]={-5, 9 ,-5, 11 ,20};
printf("%d\n",solve(data,10));
return 0;
}
