14
3
You will be given a 2-D array A of integers, and a length N. Your task is to find within the array the straight line (horizontal, vertical or diagonal) of N elements that yields the highest total sum, and return that sum.
Example
N = 3, A =
3 3 7 9 3
2 2 10 4 1
7 7 2 5 0
2 1 4 1 3
This array has 34 valid lines, including
Vertical
[3] 3 7 9 3
[2] 2 10 4 1
[7] 7 2 5 0
2 1 4 1 3 [3,2,7] = 12
Horizontal
3 3 7 9 3
2 2 10 4 1
7 7 [2] [5] [0]
2 1 4 1 3 [2,5,0] = 7
Diagonal
3 3 [7] 9 3
2 2 10 [4] 1
7 7 2 5 [0]
2 1 4 1 3 [7,4,0] = 11
The maximum line is
3 3 7 [9] 3
2 2 [10] 4 1
7 [7] 2 5 0
2 1 4 1 3 [7,10,9] = 26
Note: lines may not wrap around the edges of the array.
Inputs
- A X by Y 2-D array A, with X,Y > 0. Each element of the array contains an integer value which may be positive, zero or negative. You may accept this array in an alternative format (e.g. list of 1-D arrays) if you wish.
- A single, positive integer N, no greater than max(X,Y).
Output
- A single value representing the maximal line sum that can be found in the array. Note that you do not need to provide the individual elements of that line or where it is located.
Test cases
N = 4, A =
-88 4 -26 14 -90
-48 17 -45 -70 85
22 -52 87 -23 22
-20 -68 -51 -61 41
Output = 58
N = 4, A =
9 4 14 7
6 15 1 12
3 10 8 13
16 5 11 2
Output = 34
N = 1, A =
-2
Output = -2
N = 3, A =
1 2 3 4 5
Output = 12
N = 3, A =
-10 -5 4
-3 0 -7
-11 -3 -2
Output = -5
Could you add a test case where the resulting output is negative? Like
[[-10, -5, 4],[-3, 0, -7],[-11,-3,-2]]
->-5
(4 + -7 + -2
) – Kevin Cruijssen – 2017-10-17T08:01:24.753@KevinCruijssen Sure, added – user2390246 – 2017-10-17T08:16:58.910
1By the way: all answers with an explanation will gain an upvote from me, but otherwise I have no way of judging languages that I'm not familiar with (and that's most of them). – user2390246 – 2017-10-17T10:24:12.227