# Algorithms: Largest Sum Contiguous Subarray

Most of the algorithmic tasks are related to iterating over arrays of data. They often can be expressed as a function which takes some input and returns some single value or an array of values. For instance:

```
def maxSum(a: Array[Int]): Array[Int] = ???
```

Let's solve next task using Scala's elegant and concise syntax.

### Find the max sum in the given array

It is one of the interesting task that I met first time at one of my past job 5 years ago. It was an internal meetup of developers learning new languages as well as training themselves in programming for fun.

Later I use this task in Scala pet-project, called DevGym. Project idea was similar to well-known Codility web-site.

### Task

There is one array as input and another array as output. See test examples below:

```
// Given
Array(2, -4, 2, -1, 3, -3, 10, -1, -11, -100, 8, -1)
// Then
Array(2, -1, 3, -3, 10)
```

2 - 1 + 3 - 3 + 10 = 11

Since `11`

is the max sum we could find within the input array

```
//Given
Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)
//Then
Array(4, -1, 2, 1)
```

4 - 1 + 2 + 1 = 6

`6`

is the max sum.

### Solution

In general, we can solve this problem in O(n) complexity. By using intermediate variables to
accumulate current sum as well as max sum, we can find `left`

and `right`

indices, which can be used
to return a sub-array.

```
def maxSum(a: Array[Int]): Array[Int] = {
var currentSum = 0
var maxSum = 0
var left, right, maxLeft, maxRight = 0
var maxI = 0 //used when all negatives in the array
for (i <- a.indices) {
currentSum += a(i)
if (currentSum > 0) {
// in case current sum is getting greater,
// then we found next right index with the max sum so far
if (currentSum > maxSum) {
maxSum = currentSum
right = i
maxRight = right
maxLeft = left
}
} else {
// in case new sum is lower than or equal 0,
// then we need to move left and right index further
// and continue the search
left = i + 1
right = left
currentSum = 0
if (a(i) > a(maxI)) maxI = i
}
}
// at this point we found left and right
// indices to capture sub-array with max sum
if (maxLeft == a.length) Array(a(maxI))
else a.slice(maxLeft, maxRight + 1)
}
```

Above algorithm can be even shorter, if we return only final sum, i.e. without tracking left and right indices.

# Summary

Scala is a nice language to solve different algorithmic tasks. Try your next project in Scala, you will be surprised how fun to write code in it.

See my other blog-posts for algorithms in Scala: