Find the subarray maximum and the instance code

  • 2020-04-01 21:36:42
  • OfStack

Topic:
Enter an array of integers, both positive and negative.
One or more consecutive integers in an array form a subarray, each of which has a sum.
Find the maximum value of the sum of all subarrays. The time complexity is order n.

For example, the input array is 1, -2, 3, 10, -4, 7, 2, -5, and the largest subarray is 3, 10, -4, 7, 2, -5,
So the output is the sum of 18 of that subarray.

Find the state transition equation, dp[I] represents the maximum sum of the subarray containing I in the previous I number. Either the ith number has to be the largest of its own, or it has to be associated with the largest sum of the subarray containing I -1 (that is, dp[I -1]).
The dp [I] = Max {arr [I], dp [I - 1) + arr [I]}.

The code is as follows;


#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int res(int* arr, int len){
    //Learn a way to define minimum Numbers :)
    int max = -(1<<31);
    int i;
    for(i=1;i<len;i++){
        arr[i] = max(arr[i],arr[i-1]+arr[i]);
        if(max < arr[i]) max = arr[i];
    }
    return max;
}
int main(){
    int arr[] = {1,-2,3,10,-4,7,2,-5};
    printf("%dn",res(arr,8));
    return 0;
}


Related articles: