C Programming -- the solution of dynamic programming of "the sum of the largest subarray"

C Programming --“ Sum of the largest subarray ” The solution of dynamic programming

 1. The sum of the largest subarrays

example 1： Array int a1[5] = { -1, 5, 6, -7, 3 }; The sum of its largest subarray is ：5+6=11
example 2： Array int a2[5] = { -5, -4, -8, -1, -10 }; The sum of its largest subarray is ：-1
example 3： Array int a3[5] = { -1, 5, 6, -7, 10 }; The sum of its largest subarray is ：5+6-7+10=14

   Function realization ：

# include <stdio.h>
# include <string.h>
int MaxSum(int* arr, int size)
{
    
    int current = arr[0]; // Current array maximum sum 
    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); // This should return  -1, 
    max3 = MaxSum(a3, 5);
	printf("max1=%d,max2=%d,max3=%d\n",max1,max2,max3);
}

 2. Get the subscripts of the beginning and end of the largest subarray

   If I need to return the value, return the subscript of the beginning and end of the largest subarray , How do you modify this program ？

example 1： Array int a1[5] = { -1, 5, 6, -7, 3 }; The sum of its largest subarray is ：5+6=11; The start and end subscripts of the largest subarray are ：1 2.
example 2： Array int a2[5] = { -5, -4, -8, -1, -10 }; The sum of its largest subarray is ：-1; The start and end subscripts of the largest subarray are ：3 3.
example 3： Array int a3[5] = { -1, 5, 6, -7, 10 }; The sum of its largest subarray is ：5+6-7+10=14 ; The start and end subscripts of the largest subarray are ：1 4.
example 4： Array int a3[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4}; The sum of its largest subarray is ：4+(-1)+2+1=6 ; The start and end subscripts of the largest subarray are ：3 6.

   Function realization ：

#include <stdio.h>
#include <stdlib.h>
void solution(int m, int *arr){
    
    int current=arr[0];
    int max=current;
    int start=0,end=0;
    int i=0;
    /* Calculate the sum of the largest subarrays */
    for(i=1;i<m;i++)
    {
    
        if (current < 0)current = 0;   
        current += arr[i];
        if(current>max)
        {
    
            max = current;
            end=i;// The end subscript of the largest subarray 
        }
    }
	int temp=max;
	/* Calculate the end subscript of the largest subarray */
    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(" Enter the number ：");
    scanf("%d", &n);
    int *arr;
    arr = (int*)malloc(n * sizeof(int));
	printf(" Input %d It's an integer :",n);
    for (int i = 0; i < n; i++)
    {
    
        scanf("%d", &arr[i]);
    }
    solution(n, arr);
    return 0;
}

   Running results ：