算法训练2

题目描述：
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
输入描述：
输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
输出描述：
所有连续子数组中和最大的值。

示例：
Input：
3
-1 2 1
Output：
3

思路&代码：

#include<stdio.h>
int sum(int num[],int size){
    int s=0;
    int i;
    for(i=0;i<size;i++){
        s=s+num[i];
    }
    return s;   
}
int min(int a[],int size)
{
    int i,j;
    float temp;
    for(i=0;i<size-1;i++)
            for(j=i+1;j<size;j++)
                if(a[i]<a[j])
                {
                   temp=a[i];
                   a[i]=a[j];
                   a[j]=temp;
                }
}

main(){
    int i;
    int n,theSum,theMin;
    int theExpect;
    //定义一个长度为100000的数组（满足要求n(1 <= n <= 100000)）
    int Arr[100000];
    //输入集合中的元素个数 
    scanf("%d",&n);
    //输入集合中的元素 
    for(i=0;i<n;i++){
        scanf("%d",&Arr[i]);
    }
    //求集合中所有元素的和 
    theSum=sum(Arr,n);
    //给集合中的元素由大到小排序 
    min(Arr,n);
    //找出集合中最小的元素 
    theMin=Arr[n-1];
    //集合最大连续子数组的和最大的值既是去掉集合中最小元素后求和 
    theExpect=theSum-theMin;
    printf("%d",theExpect); 
}

运行结果：

图片.png