C/Cpp and OS
Search…
Templates and methods
DS with C
String and Array
Basic Concept in C
OS review
Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
https://leetcode.com/problems/maximum-subarray/
Explanation:
Algorithm:
1
#include <stdio.h>
2
3
int maximumSubarray(int* array, int len){
4
int tmpMax = array[0];
5
6
int finalMax = tmpMax;
7
for(int i = 1; i < len; i++){
8
if(tmpMax + array[i] < array[i]){
9
tmpMax = array[i];
10
}else{
11
tmpMax += array[i];
12
}
13
14
if(tmpMax > finalMax){
15
finalMax = tmpMax;
16
}
17
}
18
return finalMax;
19
}
Copied!
Test:
1
int main(){
2
int array[] = {1, 2, 3, 4, 5, -10, 20, 30, -40, 10};
3
int len = sizeof(array) / sizeof(array[0]);
4
5
printf("Result of Maximum Subarray is : %d \n", maximumSubarray(array, len));
6
7
return 0;
8
}
Copied!
Copy link