C編程：“最大子數(shù)組的和” 的動(dòng)態(tài)規(guī)劃的解法

C編程筆試 --“最大子數(shù)組的和” 的動(dòng)態(tài)規(guī)劃的解法

?1.最大子數(shù)組之和

例1：數(shù)組int a1[5] = { -1, 5, 6, -7, 3 };其最大子數(shù)組之和為：5+6=11
例2：數(shù)組int a2[5] = { -5, -4, -8, -1, -10 };其最大子數(shù)組之和為：-1
例3：數(shù)組 int a3[5] = { -1, 5, 6, -7, 10 };其最大子數(shù)組之和為：5+6-7+10=14

??功能實(shí)現(xiàn)：

# include 
# include 
int MaxSum(int* arr, int size)
{
    int current = arr[0]; //當(dāng)前數(shù)組最大和
    int max = current;

    for (int i = 0; i < size; i++)
    {
        if (current < 0)
            current = 0;
        current += arr[i];
        if (current > max)
            max = current;
    }
    return max;
}

int main(void)
{
    char x[40], y[40];

    int a1[5] = { -1, 5, 6, -7, 3 };
    int a2[5] = { -5, -4, -8, -1, -10 };
    int a3[5] = { -1, 5, 6, -7, 10 };

    int max1, max2, max3;
    max1 = MaxSum(a1, 5);
    max2 = MaxSum(a2, 5); //這個(gè)應(yīng)該返回 -1， 
    max3 = MaxSum(a3, 5);
	printf("max1=%d,max2=%d,max3=%d\n",max1,max2,max3);
}

?2.獲取最大子數(shù)組的開(kāi)始和結(jié)束的下標(biāo)

??如果我需要返回值返回這個(gè)最大子數(shù)組的開(kāi)始和結(jié)束的下標(biāo)，你要怎么修改這個(gè)程序？

例1：數(shù)組int a1[5] = { -1, 5, 6, -7, 3 };其最大子數(shù)組之和為：5+6=11；最大子數(shù)組開(kāi)始和結(jié)束下標(biāo)為：1 2。
例2：數(shù)組int a2[5] = { -5, -4, -8, -1, -10 };其最大子數(shù)組之和為：-1；最大子數(shù)組開(kāi)始和結(jié)束下標(biāo)為：3 3。
例3：數(shù)組 int a3[5] = { -1, 5, 6, -7, 10 };其最大子數(shù)組之和為：5+6-7+10=14 ； 最大子數(shù)組開(kāi)始和結(jié)束下標(biāo)為：1 4。
例4：數(shù)組 int a3[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};其最大子數(shù)組之和為：4+(-1)+2+1=6 ； 最大子數(shù)組開(kāi)始和結(jié)束下標(biāo)為：3 6。
??功能實(shí)現(xiàn)：

#include 
#include 
void solution(int m, int *arr){
    int current=arr[0];
    int max=current;
    int start=0,end=0;
    int i=0;
    /*計(jì)算最大子數(shù)組之和*/
    for(i=1;imax)
        {
            max = current;
            end=i;//最大子數(shù)組結(jié)束下標(biāo)
        }
    }
	int temp=max;
	/*計(jì)算最大子數(shù)組結(jié)束下標(biāo)*/
    for(i=end;i>=0;i--)
    {
	  temp-=arr[i];
      if(temp<=0 || temp>max)break;
    }
	if(i<0)i=0;
    start=i;
    printf("%d,%d %d\n",max,start,end);
}
int main() {
    int n;
	printf("輸入個(gè)數(shù)：");
    scanf("%d", &n);
    int *arr;
    arr = (int*)malloc(n * sizeof(int));
	printf("輸入%d個(gè)整數(shù):",n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    solution(n, arr);
    return 0;
}
;i++)>

??運(yùn)行結(jié)果：