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;
}