A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Maximum Subarray page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

- Jeremy Grifski

Given an array, the maximum subarray is the subarray which gives the maximum sum possible in the array. Kadane's algorithm is a popular algorithm used to find out this maximum sum value.

Note: A subarray is any continuous portion of an array.

For example:

Given array: `[-1, -2, 1, 2, 3, 4, 5, 23]`

Max sum value of a subarray: `38`

Explanation: The subarray `[1, 2, 3, 4, 5, 23]`

gives the max sum value. `(1 + 2 + 3 + 4 + 5 + 23 = 38)`

You must write an executable program that accepts a string of comma separated integers on `standard input`

via the sys args, and outputs the maximum subarray sum value to `standard output`

.

Note that the Kadane's algorithm assumes that there is atleast 1 negative integer in the array. If there is no negative integer, then the max subarray sum value is the sum of all the elements of the array.

Also note that if the input string is empty, then the output is "Usage: Please provide a list of at least two integers to sort in the format: '1, 2, 3, 4, 5'".

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Maximum Subarray. In order to keep things simple, we split up the testing as follows:

- Maximum Subarray Valid Tests
- Maximum Subarray Invalid Tests

Description | Input | Output |
---|---|---|

Sample Input: One Element | "1" | "1" |

Sample Input: Many Positive Values | "1, 2, 3" | "6" |

Sample Input: Many Negative Values | "-1, -2, -3" | "-1" |

Sample Input: Many Negative Followed By Positive Values | "-2, -1, 3, 4, 5" | "12" |

Sample Input: Many Alternating Positive And Negative Values | "-1, -4, 2, 3, -3, -4, 9" | "9" |

Description | Input |
---|---|

No Input | |

Empty Input | "" |

All of these tests should output the following:

```
Usage: Please provide a list of integers in the format: "1, 2, 3, 4, 5"
```

- Maximum Subarray in Algol68
- Maximum Subarray in Commodore Basic
- Maximum Subarray in Euphoria
- Maximum Subarray in Mathematica
- Maximum Subarray in Php
- Maximum Subarray in Python
- Maximum Subarray in Rust