2020.08.16大疆嵌入式B卷第一道编程题

#include <stdio.h>
/*
 *@function:找出数组中连续子数组最大和
 *@param     arr: 数组指针
 *@param    size: 数组长度
 *@param    left: 返回连续子数组的左下标
 *@param   right: 返回连续子数组的右下标
 *@retval:整数串中连续子数组最大和
 */
int seek_max_string(int arr[], int size, int *left, int *right)
{
	int a,b,max = -0x7fffffff,ans=0;
	for(int i=0; i<size; i++)
	{
		for(int j=i; j<size; j++)
		{
			ans += arr[j];
			if(ans > max)
				max=ans,*left=i,*right=j;
		}
		ans=0;
	}
	return max;
}

/*
 *@function:找出数组下标从left->right中最小值
 *@param     arr: 数组指针
 *@param    left: 左下标
 *@param   right: 右下标
 *@retval:数组中最小值
 */
int seek_min_number(int arr[], int left, int right)
{
	int min=0x7fffffff;
	for(int i=left; i<=right; i++)
	{
			if(min > arr[i])
				min=arr[i];
	}
	return min;
}


int main()
{
	int N;
	while(scanf("%d",&N) != EOF){
		int arr[N];
		for(int i=0; i<N; i++)
			scanf("%d",&arr[i]);

		int left,right,max,min;
		int a,b,c,d,second_max=0,third_max=0,sub_max=0;//sub_max:第二个子串和最大值
		
		max = seek_max_string(arr, N, &left, &right);
		min = seek_min_number(arr, left, right);
		
		/*
		 *找到的子数组分四种情况（1）子数组在数组中间（2）子数组就是数组（3）子数组在数组最左（4）子数组在数组最右
		 *四种情况分别找寻第二子数组
		 */
		if(left != 0 && right != N-1)
		{
			second_max = seek_max_string(arr,         left-1,    &a, &b);
			third_max  = seek_max_string(arr+right+1, N-right-1, &c, &d);
			sub_max = second_max>third_max? second_max:third_max;
		}
		else if(left == 0 && right == N-1){
			sub_max = 0;
		}
		else if(left != 0 && right == N-1){
			second_max = seek_max_string(arr,     left,   &a, &b);
			sub_max = second_max;
		}
		else if(left == 0 && right != N-1){
			int *left_arr = arr;
			third_max  = seek_max_string(left_arr+right+1, N-right-1, &c, &d);
			sub_max = third_max;
		}		
		

		
		
		if(min+sub_max >= 0 || (max < 0 && sub_max<0)) //  需要找两个子数组 
			printf("%d\n", max+sub_max);
		else                               //  找到的第一个数组包含两个最大子数组
			printf("%d\n", max-min);

	}
	return 0;
}