Amazon Interview Question
Software Engineer / Developersdef maxSubarray(arr:Array[Int]): Array[Int]= {
var maxEndedArr = new Array[Int](arr.length)
var maxArr = new Array[Int](arr.length)
maxEndedArr(0) = max(0, arr(0))
maxArr(0) = max(0, arr(0))
var index = 1;
while( index < arr.length ){
val value = arr(index)
maxEndedArr(index) = max(0, maxEndedArr(index-1) + value)
maxArr(index) = max( maxArr(index-1), maxEndedArr(index) )
index += 1
}
val maxSumValue = maxArr( maxArr.length-1)
var i = maxEndedArr.length-1
var from = -1
var to = -1
while( i >=0 && from < 0 ){
if( maxEndedArr(i) == maxSumValue ){
to = i
}
if( maxEndedArr(i) == 0 && to > 0 ){
from = i+1
}
i -= 1
}
val maxSubarray = new Array[Int](to - from + 1)
var copyIndex = 0
while( from+copyIndex < to + 1 ){
maxSubarray(copyIndex) = arr(from+copyIndex)
copyIndex += 1
}
return maxSubarray
}
Optimized version:
/**
* Use one pass by original array.
* Time: O(N)
* Space: O(N)
*/
def maxSubarray(arr:Array[Int]): Array[Int]= {
if( arr == null ){
throw new IllegalArgumentException("NULL array passed")
}
if( arr.length == 0 ){
return new Array[Int](0)
}
var maxEnded = max(0, arr(0))
var maxAll = max(0, arr(0))
var firstNonZeroIndex = -1
var maxFromIndex = -1
var maxToIndex = -1
for( i <- 1 to arr.length-1){
var newMaxEnded = max(0, maxEnded + arr(i) )
var newMaxAll = max( maxAll, newMaxEnded )
if( maxEnded == 0 && newMaxEnded > 0 ){
firstNonZeroIndex = i
}
if( newMaxEnded > maxAll ){
maxFromIndex = firstNonZeroIndex
maxToIndex = i
}
maxEnded = newMaxEnded
maxAll = newMaxAll
}
// up to N elements
val maxSubarray = new Array[Int](maxToIndex - maxFromIndex + 1)
for( i <- 0 to maxSubarray.length-1 ){
maxSubarray(i) = arr(maxFromIndex + i)
}
return maxSubarray
}
After sorting leave first element and return the pointer of rest of the array. Does it meet your requirement? Or I misunderstood it?
Just keep track of current maximum sum, if the current element alone is bigger than the sum, then update the sum with current element.
See the code below in action: ideone.com/bPblj
int GetMaxSum(const vector<int>& array, int* max_lb, int* max_ub) {
int maxsum = std::numeric_limits<int>::min();
int sum = 0;
int lb = 0;
*max_lb = *max_ub = lb;
int len = array.size();
for (int i = 0; i < len; ++i) {
sum += array[i];
if (sum < array[i]) {
sum = array[i];
lb = i;
}
if (maxsum < sum) {
maxsum = sum;
*max_lb = lb;
*max_ub = i;
}
}
return maxsum;
}
#include<stdio.h>
int main()
{
int arr[13]={-11,-2,6,4,5,10,7,-9,11,15,16,-5,-8};
int previous_sum=0;
int current_sum=0;
int i=0;
for(i=0;i<13;i++)
{
if(arr[i]<0)
{
if(previous_sum<=current_sum)
previous_sum=current_sum;
current_sum=0;
}
else
{
current_sum=current_sum+arr[i];
}
}
if(previous_sum>=current_sum)
{
current_sum=previous_sum;
}
printf("Value is %d\n",current_sum);
}
For contiguous subarray. how about use kadane's algorithm.
- jproboy July 21, 2011