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

?1.最大子數組之和

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

??功能實現：

# include 
# include 
int MaxSum(int* arr, int size)
{
    int current = arr[0]; //當前數組最大和
    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); //這個應該返回 -1， 
    max3 = MaxSum(a3, 5);
	printf("max1=%d,max2=%d,max3=%d\n",max1,max2,max3);
}

?2.獲取最大子數組的開始和結束的下標

??如果我需要返回值返回這個最大子數組的開始和結束的下標，你要怎么修改這個程序？

例1：數組int a1[5] = { -1, 5, 6, -7, 3 };其最大子數組之和為：5+6=11；最大子數組開始和結束下標為：1 2。
例2：數組int a2[5] = { -5, -4, -8, -1, -10 };其最大子數組之和為：-1；最大子數組開始和結束下標為：3 3。
例3：數組 int a3[5] = { -1, 5, 6, -7, 10 };其最大子數組之和為：5+6-7+10=14 ； 最大子數組開始和結束下標為：1 4。
例4：數組 int a3[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};其最大子數組之和為：4+(-1)+2+1=6 ； 最大子數組開始和結束下標為：3 6。
??功能實現：

#include 
#include 
void solution(int m, int *arr){
    int current=arr[0];
    int max=current;
    int start=0,end=0;
    int i=0;
    /*計算最大子數組之和*/
    for(i=1;imax)
        {
            max = current;
            end=i;//最大子數組結束下標
        }
    }
	int temp=max;
	/*計算最大子數組結束下標*/
    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("輸入個數：");
    scanf("%d", &n);
    int *arr;
    arr = (int*)malloc(n * sizeof(int));
	printf("輸入%d個整數:",n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    solution(n, arr);
    return 0;
}
;i++)>

??運行結果：