Service Now Interview Question
Staff EngineersCountry: United States
Interview Type: In-Person
Linear Time approach :
def maxSubArray(nums):
curr_sum = nums[0]
max_sum = nums[0]
for i in range(1,len(nums)):
curr_sum += nums[i]
if curr_sum < nums[i]:
curr_sum = nums[i]
max_sum = max(max_sum, curr_sum)
return max_sum
For further read :
http://worldkosh.com/blog/2018/09/13/largest-sum-subarray/
public class ArrayBiggestSum {
public static void main(String[] args) {
int biggestSum = 0;
int[] intArr = { 1, 3, 5, 7, 7, 8, 8, 9, -2, 14, -5, 0, 4 };
for (int i = 0; i < intArr.length; i++) {
for (int j = i + 1; j < intArr.length; j++) {
if (intArr[i] + intArr[j] > biggestSum) {
biggestSum = intArr[i] + intArr[j];
}
}
}
System.out.println(biggestSum);
}
}
Output -
23
A straightforward application of Kadane's algorithm. Sharing my solution in Python below:
Test code
- prudent_programmer September 14, 2018