求最長子序列和

[cpp
#include <stdio.h>  
#include <stdlib.h>  
 
int sub_Sum(int a[], int left, int right) 
{ 
    int i, temp_sum = 0; 
    for(i = left; i <= right; i++) 
    { 
        temp_sum += a[i]; 
    } 
    return temp_sum; 
} 
 
int main() 
{ 
    int i, j, k, len; 
    int max_sum = 0, cur_sum = 0; 
    printf("Please input the length of the sequence: \n"); 
    scanf("%d\n", &len); 
    int *a = (int *)malloc(len * sizeof(i)); 
 
    for(i = 0; i < len; i++) 
    { 
        scanf("%d", &a[i]); 
    } 
 
    for(i = 0; i < len; i++) 
    { 
        for(j = i; j < len; j++) 
        { 
            for(k = i; k <= j; k++) 
            { 
                cur_sum += a[k]; 
            } 
            if(cur_sum > max_sum) 
                max_sum = cur_sum; 
            cur_sum = 0; 
        } 
    } 
    printf("Max sum is : %d\n", max_sum); 
 
   max_sum = 0; 
    for(i = 0; i < len; i++) 
    { 
        for(j = i; j < len; j++) 
        { 
            cur_sum = sub_Sum(a, i, j); 
            if(cur_sum > max_sum) 
                max_sum = cur_sum; 
            cur_sum = 0; 
        } 
    } 
    printf("Max sum is : %d\n", max_sum); 
 
    free(a); 
    return 0; 
} 

#include <stdio.h>
#include <stdlib.h>

int sub_Sum(int a[], int left, int right)
{
    int i, temp_sum = 0;
    for(i = left; i <= right; i++)
    {
        temp_sum += a[i];
    }
    return temp_sum;
}

int main()
{
    int i, j, k, len;
    int max_sum = 0, cur_sum = 0;
    printf("Please input the length of the sequence: \n");
    scanf("%d\n", &len);
    int *a = (int *)malloc(len * sizeof(i));

    for(i = 0; i < len; i++)
    {
        scanf("%d", &a[i]);
    }

    for(i = 0; i < len; i++)
    {
        for(j = i; j < len; j++)
        {
            for(k = i; k <= j; k++)
            {
                cur_sum += a[k];
            }
            if(cur_sum > max_sum)
                max_sum = cur_sum;
            cur_sum = 0;
        }
    }
    printf("Max sum is : %d\n", max_sum);

   max_sum = 0;
    for(i = 0; i < len; i++)
    {
        for(j = i; j < len; j++)
        {
            cur_sum = sub_Sum(a, i, j);
            if(cur_sum > max_sum)
                max_sum = cur_sum;
            cur_sum = 0;
        }
    }
    printf("Max sum is : %d\n", max_sum);

    free(a);
    return 0;
}

法二：O(n^2)

[cpp]

#include <stdio.h>  
#include <stdlib.h>  
 
int main() 
{ 
    int i, j, len; 
    int cur_sum = 0, max_sum = 0; 
    printf("Please input the length of the sequence : \n"); 
    scanf("%d\n", &len); 
    int *a = (int *)malloc(len * sizeof(int)); 
    for(i = 0; i < len; i++) 
    {    
        scanf("%d", &a[i]); 
    }    
    for(i = 0; i < len; i++) 
    {    
        //計算一次以i開始的最大和值  
        for(j = i; j < len; j++) 
        {    
            cur_sum += a[j]; 
            if(cur_sum > max_sum) 
            {    
                max_sum = cur_sum; 
            }    
        }    
        cur_sum = 0; 
    }    
    printf("The max sum is: %d\n", max_sum); 
    free(a); 
 
    return 0; 
} 

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, j, len;
    int cur_sum = 0, max_sum = 0;
    printf("Please input the length of the sequence : \n");
    scanf("%d\n", &len);
    int *a = (int *)malloc(len * sizeof(int));
    for(i = 0; i < len; i++)
    {  
        scanf("%d", &a[i]);
    }  
    for(i = 0; i < len; i++)
    {  
        //計算一次以i開始的最大和值
        for(j = i; j < len; j++)
        {  
            cur_sum += a[j];
            if(cur_sum > max_sum)
            {  
                max_sum = cur_sum;
            }  
        }  
        cur_sum = 0;
    }  
    printf("The max sum is: %d\n", max_sum);
    free(a);

    return 0;
}