#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
int* array(int n)
{
    int* num;
    int i;
    srand(time(0));
   
    num = (int*)malloc(sizeof(int) * n);
    if(num == NULL)    return NULL;
   
   
    for(i = 0 ; i < n ; i++)
    {
        num[i] = (int)pow(-1 , rand() %100) * rand()%100;
    }
   
    return num;
}

void print(int* num , int i)
{
    int j;
    for(j = 0 ; j < i ; j++)
    {
        printf("%d " , num[j]);
    }
    printf("\n");
}

void superPower(int* num , int numberOfArrary)
{
    int i , j , temp  , max , k;
   
    max = -100;
    for(i = 0 ; i < numberOfArrary ; i++)
    {
        for(j = i ; j <= numberOfArrary ; j++)
        {
            temp = num[i];
            for(k = i + 1 ; k < j ; k++)
            {
                temp += num[k];
            }
            
            if(temp > max)    max = temp;
        }
    }
   
    printf("最大子段和为：%d" , max);
}

int Find_Max_Crossing_SubArray(int* A, int start, int mid, int end)
{
    int leftSum = -100;
    int reghtSum = -100;
    int sum = 0;
    int i;
   
    for(i = mid ; i >= start ; i--)
    {
        sum += A[i];
        if(leftSum < sum)    leftSum = sum;
    }
   
    for(i = mid + 1 , sum = 0; i <= end ; i++)
    {
        sum += A[i];
        if(reghtSum < sum)    reghtSum = sum;
    }
   
    return reghtSum + leftSum;
}

int Find_Maximum_SubArray(int* A, int start, int end)
{
    int leftSum , reghtSum , midSum;
    if(start == end)
    {
        return A[end];
    }
    else
    {
        int mid = (start + end) / 2;
        leftSum = Find_Maximum_SubArray(A , start , mid);
        reghtSum = Find_Maximum_SubArray(A , mid + 1 , end);
        midSum = Find_Max_Crossing_SubArray(A , start , mid , end);
        
        if(leftSum >= reghtSum && leftSum >= midSum)
        {
            return leftSum;
        }
        else
        {
            if(reghtSum >= leftSum && reghtSum >= midSum)
            {
                return reghtSum;
            }
            else    return midSum;
        }
    }
}

int main()
{
    int* num;
    int start = clock();
    int numberOfArrary , i;
   
    printf("请输入数组长度:");
    scanf("%d" , &numberOfArrary);
   
    num = array(numberOfArrary);
    print(num , numberOfArrary);
   
    superPower(num , numberOfArrary);
    printf("\n");
    printf("最大子段和为：%d" , Find_Maximum_SubArray(num , 0 , numberOfArrary));
   
   
   
   
    int end = clock();
    printf("\n\n运行时间为：%d 毫秒" , end - start);
   
   
    return 0;
}

void superPower(int* num , int numberOfArrary)
{
    int i , j , temp  , max , k;

 

    max = -100;
    for(i = 0 ; i < numberOfArrary ; i++)
    {
        temp = num[i];
        for(j = i + 2 ; j <= numberOfArrary ; j++)
        {
            for(k = i + 1 ; k < j ; k++)
            {
                temp += num[k];
            }
          

            if(temp > max)    max = temp;
        }
    }

 

    printf("最大子段和为：%d" , max);
}