Yahoo Microsoft Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Implementation of Kadane's algorithm
#include<iostream>
#include<stdio.h>
using namespace std;
void printSubArray(int arr[],int start,int end) {
for(int i=start;i<=end;i++) {
cout<<arr[i]<<" ";
}
return;
}
void kadaneAlgo(int arr[],int size) {
int maxIndex;
int startIndex=0;
int maxStartIndex;
int currSum=0;
int max=arr[0];
for(int i=0;i<size;i++) {
currSum=currSum+arr[i];
if(currSum<=0) {
currSum=0;
startIndex=i+1;
}
else {
if(currSum>max) {
max=currSum;
maxIndex=i;
maxStartIndex=startIndex;
}
}
}
printSubArray(arr,maxStartIndex,maxIndex);
}
int main() {
int arr[]={-2, 11, -4, 13, -5, -2};
kadaneAlgo(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}
Divide and conquer ...
Recursively find the max sum in left half of the array and in the right half of the array.
Determine the max of Lsum,Rsum and Lsum+Rsum.
I don't know why they need an nlogn while we have o(n) solution in DP.
good solution @algos
Adding one more:
if input contains all negatives it returns 0. To handle this add extra check that will look all numbers are negative, if they are it will return max of them (or smallest in terms of absolute value)
Python code handling the case when all the integers are negative,
def max_subarray(arr):
max_ending_here = max_so_far = arr[0]
for x in arr:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_ending_here, max_so_far)
return max_so_far
O(n) Kadanes algorithm.
public static int maxSumSubArray(final int[] a) {
int maxSum = 0;
int maxSoFar = 0;
int tempBegin = 0;
int begin = 0;
int end = 0;
for (int i = 0; i < a.length; i++) {
maxSoFar += a[i];
if (maxSoFar < 0) {
maxSoFar = 0;
tempBegin = i + 1;
} else if (maxSoFar > maxSum) {
maxSum = maxSoFar;
begin = tempBegin;
end = i;
}
}
for (int i = begin; i <= end; i++) {
System.out.print(a[i] + ", ");
}
return maxSum;
}
Yeah, and I never learned it. I had it thrown at me with like 5 mins to spare. After floundering with two loops and really not hitting the mark he gently let me know it was time and we ended the call. Hoping my +1s in other areas keep me in the hunt.
here is the solution in Python:
def solution(A):
# write your code in Python 2.6
if len(A) == 0:
return -1
A.sort()
leaderDict = {} #-- used to index counts for each value
winner = -1
for i in xrange(0, len(A)):
count = 1
if A[i] in leaderDict:
count = leaderDict[A[i]] + 1
leaderDict[A[i]] = count
if winner < 0 or count > leaderDict[winner]:
winner = A[i]
if winner in leaderDict:
if leaderDict[winner] > len(A)/2:
return winner
return -1
It seems there is a mistake in the question --
{5,6,-4,3} = 0,1; {8,9,-6,0,3,9} = 1, 5
the first example looks correct, but the second one would be 0,5 not 1,5.
Sum(0-5) = 23
Sum(1-5) = 15.
Thanks to Anonymous for pointing out at error in my my original and to S.Abakumoff for pointing out that the original algorithm requires at least one positive number. This solution addresses both comments:
Kadane's algorithm is the go-to solution for the maximum subarray problem. It is an iterative solution which runs in O(n) time. It finds largest subarray at each index i of array A, starting at index zero and iterates through the entire array. By using the knowledge of the previous largest subarray in combination with the knowledge that a previous subarray's sum can only be increased with a positive number at the next contiguous index, we can find the maximum contiguous subarray of A.
Consider the integer array A of size n where A contains at least one positive number (I'll handle the case where it doesn't at the end). To do this, we need to track 2 things: the current maximum subarray's sum and the maximum subarray which ends at index i. We’ll call them overallMax and maxEndingHere, respectively.
For each index, we set maxEndingHere equal to A[i] + the previous index's maxEndingHere. If it's not positive, we reset maxEndingHere equal to 0. Finally, we compare the value of maxEndingHere with overallMax and take the larger of the two numbers for our new overallMax. Note that in the actual algorithm, we would want to keep track of the current set of indices representing the overallMax. We would also make sure that array was not empty.
Here is a simple example: {6,-10,12}
overallMax =0
maxEndingHere=0
Start
A[0]:
maxEndingHere =Math.max(0, maxEndingHere + A[0]) =Math.max(0, 0 + 6)=6
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6
A[1]:
maxEndingHere =Math.max(0, maxEndingHere + A[1]) =Math.max(0,6-10)=0
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6
A[2]:
maxEndingHere=Math.max(0, 0 + A[2])=Math.max(0,12)=12
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(6,12)=12
End
In the scenario where there are all negative numbers, I believe we could temporarily make all the numbers positive and use Math.min instead of Math.max to achieve the same result.. Then, at the end, we could return all the numbers to negatives and find the sum of the values given by our negative numbers between the indices of our max subarray.
I don't see how this logic can work if you replace the number -1 in your last example with any number smaller than -2 (for example -9).
Your algorithm would give the array {2,-9,4} which has a smaller sum than {4}.
Unless I'm missing something here...
If you were to replace -1 with -9, I think the algorithm would return {4}. It would get 2 from A[0], then it would have a choice between 2, -9, and -7 at A[1]. It would choose 2. At A[2], it would choose 4 since it is bigger than the previous max of 2 and similarly at A[3] it would choose 4. I should clarify that your algorithm needs to keep track of the current max subarray for situations where the max does not end at the current index (like the case you provided).
public static int[] findMaxSubArray(int[] array, int start, int end)
{
if(start == end)
return new int[]{start, end, array[start]}; // starIndex, endIndex, and Maxsum
int mid = (start + end)/2;
int[] leftMaxSubarray = findMaxSubArray(array, start, mid);
int[] rightMaxSubarray = findMaxSubArray(array, mid +1, end);
int[] crossMaxSubarray = findCrossMaxSubArray(array, start, mid, end);
return max(crossMaxSubarray, max(leftMaxSubarray, rightMaxSubarray));
}
public static int[] max(int[] array1, int[] array2)
{
if(array1[2] > array2[2])
return array1;
return array2;
}
public static int[] findCrossMaxSubArray(int[] array, int start, int mid, int end)
{
int maxSum = Integer.MIN_VALUE;
int sum = 0;
int leftMaxIndex = mid;
for(int i = mid; i >= start; i--)
{
sum = sum + array[i];
if(sum > maxSum)
{
maxSum = sum;
leftMaxIndex = i;
}
}
sum = 0;
int maxSum2 = Integer.MIN_VALUE;
int rightMaxIndex = mid;
for(int i = mid +1; i <= end; i++)
{
sum = sum + array[i];
if(sum > maxSum2)
{
maxSum2 = sum;
rightMaxIndex = i;
}
}
return new int[]{leftMaxIndex, rightMaxIndex, maxSum + maxSum2};
}
Thought to share the questions that were asked to me in the phone interview. The questions were pretty simple.
#include<stdio.h>
#include<stdlib.h>
#define len 9
int maxs(int a[])
{
int maxcurrsum=0;
int maxsum=0;
int i=0;
int start_temp=0;
int start=0;
int end=0;
for(;i<len;i++)
{
maxcurrsum=maxcurrsum+a[i];
if(a[i]>maxcurrsum)
{
maxcurrsum=a[i];
start_temp=i;
}
if(maxcurrsum>maxsum)
{
maxsum=maxcurrsum;
start=start_temp;
end=i;
}
}
printf("%d %d\n",start,end);
for(i=start;i<end;i++)
printf("%d\n",a[i]);
return maxsum;
}
Also found in - jasmeetsingh.net/wordpress/?p=36
/*
* Source: Wikipedia
*
* In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
T
*/
package BST;
public class MaxSubArray {
int arr[] = new int[]{-2, 1, -3, -4, -1, 2, 1, -5, 4};
public MaxSubArray() {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minPointer = 0;
int maxPointer = 0;
int subArrSum = 0;
for(int i =0;i<arr.length;i++)
{
subArrSum += arr[i];
if(subArrSum<min)
{
minPointer = i;
min = subArrSum;
}
if (subArrSum>max)
{
maxPointer = i;
max = subArrSum;
}
}
minPointer++;
if(minPointer >= maxPointer)
{
min = 0;
minPointer = 0;
}
System.out.println(max - min);
for(int i = minPointer; i<=maxPointer;i++)
{
System.out.print(arr[i] + " ");
}
}
}
public class algo1 {
static int arr[] = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4,-100};
public static void main(String args[]) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minPointer = 0;
int maxPointer = 0;
int subArrSum = 0;
for(int i =0;i<arr.length;i++)
{
subArrSum += arr[i];
if(subArrSum<min)
{
minPointer = i;
min = subArrSum;
}
if (subArrSum>max)
{
maxPointer = i;
max = subArrSum;
}
}
minPointer++;
int sum2=0;
int flag=0;
if(minPointer >= maxPointer)
{
min=Integer.MAX_VALUE;
minPointer=0;
for(int i=0;i<maxPointer;i++)
{ sum2+=arr[i];
if(min>sum2) { min=sum2; minPointer=i;
}
flag=1;
}
}
//System.out.print(minPointer);
if(flag==1)
minPointer++;
//System.out.println(max - min);
for(int i = minPointer; i<=maxPointer;i++)
{
System.out.print(arr[i] + " ");
}
}
}
Tweak in jasmeet`s code .. instead of setting minptr to 0 if min>=max set it by finding the min. element just before the max element .
Python version:
def maximal_subarray(arr):
if not arr:
return []
max_sum = arr[0]
max_start = 0
max_end = 0
current_sum = arr[0]
current_start = 0
for i in range(1, len(arr)):
current_sum += arr[i]
if current_sum < arr[i]:
current_sum = arr[i]
current_start = i
if current_sum > max_sum:
max_sum = current_sum
max_start = current_start
max_end = i
return arr[max_start:max_end+1]
#include<iostream>
using namespace std;
#include<conio.h>
int main()
{
int i,s,*a,t=0,start=0,end=0,max_s=0,end1=0;
cout<<"Enter size of first array";
cin>>s;
cout<<"Enter elements in first array:";
a=new int[s];
for(i=0;i<s;i++)
cin>>a[i];
for(i=0;i<s;i++)
{
t=t+a[i];
if(t<a[i])
{
t=a[i];
start=i;
end=i;
}
else
end++;
if(t>max_s)
{
max_s=t;
end1=i;
}
}
cout<<"Max sum is:"<<max_s<<"\n";
cout<<"start"<<start<<"\t"<<"end"<<end1;
getch();
return 0;
}
#include<iostream>
using namespace std;
#include<conio.h>
int main()
{
int i,s,*a,t=0,start=0,end=0,max_s=0,end1=0;
cout<<"Enter size of first array";
cin>>s;
cout<<"Enter elements in first array:";
a=new int[s];
for(i=0;i<s;i++)
cin>>a[i];
for(i=0;i<s;i++)
{
t=t+a[i];
if(t<a[i])
{
t=a[i];
start=i;
end=i;
}
else
end++;
if(t>max_s)
{
max_s=t;
end1=i;
}
}
cout<<"Max sum is:"<<max_s<<"\n";
cout<<"start"<<start<<"\t"<<"end"<<end1;
getch();
return 0;
}
This is called Maximum Subarray Problem.
If we want O(n) time complexity then we use Kadane's Algorithm.
//Kadane's Algorithm: O(n) time
function max_subarray(Array A){
max_ending_here = max_so_far = 0;
for (each x in array A) {
max_ending_here = max(0, max_ending_here + x);
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
Another solution (using divide and conquer) with O(n log n) time complexity exists.
//Divide and Conquer: O(n log n) time, (given in CLR book)
Given an array A. We want to find maximum continuous subarray. Divide the
array into two equal halves. The maximum subarray must lie in exactly one of
the following three places:
1) entirely in the left half of the array A,
2) entirely in the right half of the array A,
3) crossing the midpoint of the array A
We can check the third possibility in linear time and we check first two
possibilities recursively.
//T(n) = 2T(n/2) + cn = O(n log n)
I tried with couple of examples and the below code snippet was giving correct result. It is not an elegant snippet though.
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] A = {8,9,-6,0,3,9}; //Maximum sum is: 23 of the elements from index 0 to 5
//int[] A = {11, 12,-28,26}; //Maximum sum is: 26 of the elements from index 3 to 3
int[] A = {11, 16,-28,31, -30, 31}; // Maximum sum is: 32 of the elements from index 3 to 5
int sum = 0;
int maxSum = 0;
int indexIL = 0;
int indexI = 0;
int indexF = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
if(sum>maxSum){
maxSum = sum;
indexF = i;
if(indexIL>indexI)
indexI = indexIL;
}
if(sum<0){
sum = 0;
indexIL = i+1;
}
}
System.out.println("Maximum sum is: "+ maxSum + " of the elements from index "+ indexI + " to "+ indexF );
}
public class MaxSum
{
public static void main(String a[])
{
MaxSum ms=new MaxSum();
ms.maxSum();
}
void maxSum() {
int[] arr = {25000,25000,900,3,7,188000,2600,120,24,89,123000};
int leftPtr = 0;
int leftPtrForMaxVal = 0;
int rightPtr = arr.length-1;
int rightPtrForMaxVal = 0;
int j=arr.length-1;
leftPtrForMaxVal=arr[0];
rightPtrForMaxVal=arr[j];
for(int i=0; i<arr.length-1;i++)
{
if(arr[i]>leftPtrForMaxVal && i!=rightPtr )
{
leftPtrForMaxVal=arr[i];
leftPtr=i;
}
if(arr[j]>rightPtrForMaxVal && j!=leftPtr )
{
rightPtrForMaxVal=arr[j];
rightPtr=j;
}
j--;
}
System.out.println("leftPtrValue : "+leftPtrForMaxVal);
System.out.println("leftPtr : "+leftPtr);
System.out.println("rightRptValue : "+rightPtrForMaxVal);
System.out.println("rightPtr : "+rightPtr);
}
}
int main()
{
int index1=0, index2=0, a;
int array1[12] = {1,2,3,4,5,6,8,7,10,4,1,2};
for(int i=0 ; i < sizeof(array1)/sizeof(int)-1 ; i++)
{
a = index1;
cout<<array1[index1]<<"index value one"<<endl;
cout<<array1[i]<<"i value"<<endl;
if(array1[index1]<array1[i+1])
{
index1 = i+1;
index2 = a;
}
}
system("pause");
return 0;
}
You should find the longest partial sequence that sums to the bigger number
//PseudoCode
//if next is positive add it to part sum
//if partSum > maxSum make part the max, adjust indeces.
//else if negative
//if (maxSum+value)>0
//if yes, we need it. Add it to the part sum.
//else reset the index to this element+1 and make partsum =0;
public class MaxPartSum {
public PartSum findPartMaxSum(int[] arr){
int partSum =0;
int maxSum = 0;
int startIndex=0;
int endIndex =0;
int i=0;
while (i<arr.length){
if (arr[i]>0) //num is positive
{
partSum += arr[i]; //increase partSum
if (partSum>maxSum){
maxSum = partSum;
endIndex = i;
}
}
else{ //num is negative or zero
if (maxSum+arr[i] > 0)
partSum+=arr[i];
else //the element doesn't help at all
{
partSum=0;
startIndex = i+1;
}
}
i++;
}
System.out.println("Max Sum: " + maxSum);
System.out.println("Index " + startIndex + " to " + endIndex);
PartSum p = new PartSum(maxSum, startIndex, endIndex);
return p;
}
class PartSum{
int maxSum;
int startIndex;
int endIndex;
public PartSum(int maxSum, int startIndex, int endIndex){
this.maxSum = maxSum;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
}
public static void main (String[] args){
MaxPartSum m = new MaxPartSum();
int[] arr = {-1, -2, 5, -2, -3};
m.findPartMaxSum(arr);
}
}
Java version of Kadane / max subarray:
public int[] indexRange(int[] array) {
int beginTemp = 0;
int begin = 0;
int end = 0;
int maxSoFar = array[0];
int maxEndingHere = array[0];
for (int i = 1; i < array.length; i++) {
if (maxEndingHere < 0) {
maxEndingHere = array[i];
beginTemp = i;
} else {
maxEndingHere += array[i];
}
// calculate maxSoFar
if(maxEndingHere >= maxSoFar) {
maxSoFar = maxEndingHere;
begin = beginTemp;
end = i;
}
}
return new int[]{begin, end, maxSoFar};
}
Simpler and Easier to understand
#include<stdio.h>
int GetLargestSubArray(int* arr, int n){
int iBeginSaved=0, iEndSaved=0; // the start/end positions of the saved sub array
int iBegin=0, iEnd=0; // the start/end positions of the current sub array
int nSumSaved=0, nSum=0; // the sums of whole saved largest and current sub arrays
int i = 0; // index to loop in the array
if (0 == n){
iEndRet = iBeginRet = -1;
return 0;
}
nSumSaved = nSum = arr[i];
for(i = 1; i < n; i++) {
/* Compute the current largest sum */
if (nSum<=0){
nSum = arr[i];
iBegin = iEnd = i;
}
else{
nSum += arr[i];
iEnd = i;
}
if (nSum > nSumSaved){
nSumSaved = nSum;
iBeginSaved = iBegin;
iEndSaved = iEnd;
}}
printf("\n%d %d",iBeginSaved,iEndSaved);
return nSumSaved;
}
int main(){
int a[]={1, -9,4, 15, -9, 0, -6, 6, -12, 2, 3};
int n=sizeof(a)/sizeof(a[0]);
printf("%d ",n);
GetSubArray(a,n,0,0);
}
Generally, we have a left index and a right index indicating the boundaries of the current window. We also have a running sum of the current window. If the running sum goes below zero, then we start a new window from right+1. Update the maxSum accordingly. It works for both negative or positive arrays.
public class Pair
{
public int first;
public int second;
public Pair(int f, int s)
{
first=f;
second=s;
}
public String toString()
{
return String.format("[Pair: first=%d, second=%d]", first, second);
}
}
public class ID5256786030362624
{
public Pair maxSubarray(int[] A)
{
if (A==null || A.length==0)
return null;
Pair result=new Pair(-1, -1);
int maxSum=Integer.MIN_VALUE;
int left=0;
int sum=0;
for (int right=0; right<A.length; right++)
{
sum += A[right];
if (sum>maxSum)
{
maxSum=sum;
result.first=left;
result.second=right;
}
if (sum<0)
{
sum=0;
left=right+1;
}
}
return result;
}
public static void main(String[] args)
{
int[] A={5,6,-4,3};
int[] B={8,9,-6,0,3,9};
int[] C={-1, -2, -5, -10};
ID5256786030362624 wpd=new ID5256786030362624();
System.out.println(wpd.maxSubarray(A));
System.out.println(wpd.maxSubarray(B));
System.out.println(wpd.maxSubarray(C));
}
}
#include "stdafx.h"
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int testCase [] = { 8, 9, -6, 0, 3, 9 };
queue<int> indexQueue;
int descendingNum = 0;
bool ascending = false;
int ascendingFinalIndex = 0;
int ascendingBeginIndex = 0;
for (int i = 0; i < 6; i++)
{
if (testCase[i] < 0)
{
if (ascending)
{
ascending = false;
ascendingFinalIndex = i - 1;
descendingNum = testCase[i];
}
else
{
descendingNum += testCase[i];
}
}
else
{
ascendingFinalIndex = i;
if (!ascending)
{
if (descendingNum > 0)
{
ascending = true;
descendingNum = 0;
ascendingFinalIndex = i;
}
}
}
}
cout << ascendingBeginIndex << "," << ascendingFinalIndex;
system("pause");
return 0;
}
#include "stdafx.h"
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int testCase [] = { 8, 9, -6, 0, 3, 9 };
queue<int> indexQueue;
int descendingNum = 0;
bool ascending = false;
int ascendingFinalIndex = 0;
int ascendingBeginIndex = 0;
for (int i = 0; i < 6; i++)
{
if (testCase[i] < 0)
{
if (ascending)
{
ascending = false;
ascendingFinalIndex = i - 1;
descendingNum = testCase[i];
}
else
{
descendingNum += testCase[i];
}
}
else
{
ascendingFinalIndex = i;
if (!ascending)
{
if (descendingNum > 0)
{
ascending = true;
descendingNum = 0;
ascendingFinalIndex = i;
}
}
}
}
cout << ascendingBeginIndex << "," << ascendingFinalIndex;
system("pause");
return 0;
}
static void Main(string[] args)
{
int[] arr = { 5, 3, 1, 9, 12 };
// this should return 0, 3 as the indexes that will produce larger sum
int Lindex = 0, Rindex = 1, sum = 0, maxSum = arr[Lindex] + arr[Rindex];
int tmp = (arr[Lindex] > arr[Rindex]) ? Lindex : Rindex;
for (int i = 1; i < arr.Length; i++)
{
tmp = (arr[Lindex] > arr[Rindex]) ? Lindex : Rindex;
sum = arr[tmp] + arr[i];
if (sum > maxSum)
{
Lindex = tmp;
Rindex = i;
maxSum = sum;
}
}
Console.WriteLine(Lindex + " , " + Rindex + " : " + maxSum);
}
void Largest_Indices(int arr[],int size)
{
int pos=0,pos1=1,i,j;
i=pos;
for(j=i+1;j<size;j++)
{
if(arr[pos]<arr[j])
{
pos1=pos;
pos=j;
}
else if(arr[pos1]<arr[j])
{
pos1=j;
}
}
printf("%d %d",pos,pos1);
}
void main()
{
int arr[]={34,67,98,21,33,21,223,12};
Largest_Indices(arr,(sizeof(arr)/sizeof(int)));
}
void Largest_Indices(int arr[],int size)
{
int pos=0,pos1=1,i,j;
i=pos;
for(j=i+1;j<size;j++)
{
if(arr[pos]<arr[j])
{
pos1=pos;
pos=j;
}
else if(arr[pos1]<arr[j])
{
pos1=j;
}
}
printf("%d %d",pos,pos1);
}
void main()
{
int arr[]={34,67,98,21,33,21,223,12};
Largest_Indices(arr,(sizeof(arr)/sizeof(int)));
}
A = [int(x) for x in raw_input().split()]
maxsofarstart = 0
maxsofarend = 0
maxsofar = A[0]
sumsofar_start = 0
sumsofar = A[0]
for i in xrange(1,len(A)):
if A[i] > sumsofar:
if sumsofar > 0: #include sumsofar
sumsofar += A[i]
else: #remove sumsofar
sumsofar_start = i
sumsofar = A[i]
else:
sumsofar = sumsofar + A[i]
if sumsofar > maxsofar:
maxsofar = sumsofar
maxsofarstart = sumsofar_start
maxsofarend = i
print maxsofarstart, maxsofarend
public class maxSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a = {8, -6, 8, -3};
//int[] a = {11, 12, -28, 26};
//int[] a = {8,9,-6,0,3,9};
int[] a = {11, 16,-28, 31, -30, 31};
int maxSumVal = 0;
int sum = 0;
int previous = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i<a.length; i++)
{
sum = sum + a[i];
if(sum > 0)
{
if(sum >= previous)
{
previous = sum;
maxSumVal = sum;
endIndex = i;
}
}
else
{
sum = 0;
startIndex = (i+1)%a.length;
}
}
System.out.println(maxSumVal);
System.out.println(startIndex);
System.out.println(endIndex);
}
}
public class maxSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a = {8, -6, 8, -3};
//int[] a = {11, 12, -28, 26};
//int[] a = {8,9,-6,0,3,9};
int[] a = {11, 16,-28, 31, -30, 31};
int maxSumVal = 0;
int sum = 0;
int previous = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i<a.length; i++)
{
sum = sum + a[i];
if(sum > 0)
{
if(sum >= previous)
{
previous = sum;
maxSumVal = sum;
endIndex = i;
}
}
else
{
sum = 0;
startIndex = (i+1)%a.length;
}
}
System.out.println(maxSumVal);
System.out.println(startIndex);
System.out.println(endIndex);
}
}
#include<iostream>
#include<stdio.h>
#define MAX 5
int main(int argv,char**argc)
{
int index,index_start,index_end;
int end_index,sum=0,sum1=0;
end_index=MAX-1;
int array[MAX];
std::cout<<"Enter data"<<std::endl;
for(index=0; index<MAX; index++)
{
std::cin>>array[index];
}
for(index=0; index<MAX-2;)
{
if(index==end_index)
{
index++;
end_index=MAX-1;
}
sum=array[index]+array[end_index];
if(sum1<sum)
{
sum1=sum;
index_start=index;
index_end=end_index;
}
end_index--;
std::cout<<"loop"<<std::endl;
}
std::cout<<index_start<<","<<index_end<<std::endl<<"sum"<<sum1<<std::endl;
}
#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<stdlib.h>
#include<math.h>
#define SIZE sizeof(arr)/sizeof(int)
#define FEL(i,a,b) for(int i=a;i<b;i++)
#define INF 1<<30
using namespace std;
int main()
{
int arr[]={5,-6,-4,-3,9,-9};
int start = 0,end = 0 ,sum = 0;int reset =0;
for(int i=0;i<6;i++)
{
sum +=arr[i];
if(sum<0)
{
sum =0;reset =i+1;
}
if(sum - arr[i] < sum)
{
start = reset;
end= i;
sum =sum+arr[i];
}
if(sum ==0)
{
reset =i+1;
}
}
cout<<start<<end;
return 0;
}
public class MaxSum {
public static void main(String[] args) {
Integer []input = {3,4,-8,9};
int loc1 = 0, loc2 = 0;
int max = input[0];
for(int i=1; i<input.length; i++)
{
if(max < input[i])
{
loc2 = loc1;
loc1 = i;
max = input[i];
}
}
if(loc1 == loc2)
loc1++;
System.out.println(loc2 + " "+loc1);
}
}
Is it a dynamic programming problem?
if a[i]...a[j] is the max subsequence of a[0]...a[n]
and a[k]...a[n] is the max subsequence of a[0]...a[n] that ends with a[n]
value[n] = a[i] + a[i+1] + ... a[j]
start[n] = i
last[n] = j
value2[n] = a[k] + a[k+1] + ... + a[n]
start2[n] = k
value2[n+1] = max(value2[n]+a[n+1], a[n+1])
start2[n+1] = (value2[n]>0)?k,(n+1)
value[n+1] = max(value[n], value2[n+1])
start[n+1] = (value[n]>value2[n+1])?start[n], start2[n+1]
last[n+1] = (value[n]>value2[n+1])?last[n],(n+1)
public class MaxSubArray {
/**
* @param args
*/
public static void main(String[] args) {
int[] data = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int[] result = findMaxSubArray(data, 0, data.length-1);
System.out.println(result[0] + " " + result[1] + " " + result[2]);
}
public static int[] findMaxCrossing(int[] A, int low, int mid, int high) {
int left_sum = -1000;
int left_index = 0;
int sum = 0;
for (int i = mid; i >= 0; i --) {
sum += A[i];
if (sum > left_sum) {
left_sum = sum;
left_index = i;
}
}
int right_sum = -1000;
int right_index = 0;
sum = 0;
for (int i = mid + 1; i < high; i++) {
sum += A[i];
if (sum > right_sum) {
right_sum = sum;
right_index = i;
}
}
int[] result = {left_index, right_index, left_sum + right_sum};
return result;
}
public static int[] findMaxSubArray(int[] A, int low, int high) {
int[] result = new int[3];
int[] resultLeft = new int[3];
int[] resultRight = new int[3];
int[] resultCross = new int[3];
if (high == low) {
result[0] = low;
result[1] = high;
result[2] = A[low];
return result;
} else {
int mid = (int) Math.floor((low + high)/2);
resultLeft = findMaxSubArray(A, low, mid);
resultRight = findMaxSubArray(A, mid + 1, high);
// (cross-low, cross-high, cross-sum) = findMaxCrossing(A, low, mid, high)
resultCross = findMaxCrossing(A, low, mid, high);
if (resultLeft[2] >= resultRight[2] && resultLeft[2] >= resultCross[2]) {
return resultLeft;
} else if (resultRight[2] >= resultLeft[2] && resultRight[2] >= resultCross[2]) {
return resultRight;
} else {
return resultCross;
}
}
}
}
Fully working Java code - handles all the cases
public class Solution {
public int maxSubArray(int[] A) {
int i=0;
int max=0;
int sum =0;
int flag = 0;
for(i=0;i< A.length;i++){
sum = sum + A[i];
if(sum < 0) {
int j=0;
if(A.length == 1)
max = A[0];
else {
for(j=0;j< A.length;j++)
{
if(A[j] > 0 ){
flag = 0;
break;
}
else flag = 1;
}
if(flag == 1){
max = A[0];
for(j=0;j< A.length-1;j++) {
if(A[j+1] >= max)
max = A[j+1];
}
}
else{
sum= 0;
}
}
}
else if(sum > max){
max = sum;
}
}
return max;
}
}
int a[] = {-2, 11, -4, 13, -5, -2};
int b[] = new int[a.length];
b[0] = 0;
int currentSum = a[0];
int sum =a[0];
int max = Integer.MIN_VALUE;
for(int i = 1; i<b.length; i++){
if(sum +a[i] > 0) sum += a[i];
currentSum = Math.max(currentSum + a[i], a[i]);
if(currentSum > max){
sum = 0;
max = currentSum;
}
}
System.out.println(max);
int a[] = {-3, -2, 11, -4, 13, -5, -2};
int sum;
int currentSum =a[0];
int max = Integer.MIN_VALUE;
for(int i = 1; i<a.length; i++){
sum = Math.max(currentSum + a[i], a[i]);
if(sum > max){
currentSum = 0;
max = sum;
}
if(currentSum +a[i] > 0) currentSum += a[i];
}
System.out.println(max);
private static int[] getMaxSubArray(int[] array) {
int max = array[0];
int maxSoFar = max;
int maxSoFarBegin = 0;
int maxSoFarEnd = 0;
for (int i = 1; i < array.length; i++) {
max = Math.max(array[i], max + array[i]);
maxSoFar = Math.max(maxSoFar, max);
if (maxSoFar == max) {
maxSoFarEnd = i;
if (max == array[i]) {
maxSoFarBegin = i;
}
}
}
return new int[]{maxSoFarBegin, maxSoFarEnd, maxSoFar, aaa(array)};
}
The key point is to add the values in the contiguous sub array until it's negative, otherwise keep adding. Here is the O(n) solution
public static int maxContinousSub(int []A) {
int maxsub = 0;
int maxsum = 0;
for (int i = 0; i < A.length; i++) {
maxsub = Math.max(maxsub+A[i], 0);
maxsum = Math.max(maxsub, maxsum);
}
return maxsum;
}
@oozz:
even negative you should not stop goal is max sum it may combination of +ve's and -ve's
@expert I meant the sum of the contiguous subarray, not array element. Check out this line:
maxsub = Math.max(maxsub+A[i], 0);
If the sum of the subarray (maxsub) is negative, we reset maxsub.
This is a working code. Compiled, tested and verified.
Your code does not work if the array only have negative values. The answer is not 0, but the largest negative. Just a minor change needed.
void maxSum(String[] args) {
int[] arr = {5,2,9,3,7,18,2,12};
int leftPtr = 0;
int leftPtrForMaxVal = 0;
int rightPtr = arr.length-1;
int rightPtrForMaxVal = 0;
while(leftPtr<rightPtr){
if(arr[leftPtr]>arr[leftPtrForMaxVal]){
leftPtrForMaxVal = leftPtr;
}
leftPtr++;
if(arr[rightPtr]>arr[rightPtrForMaxVal]){
rightPtrForMaxVal = rightPtr;
}
rightPtr--;
}
System.out.println("leftPtr : "+leftPtrForMaxVal);
System.out.println("rightRpt : "+rightPtrForMaxVal);
System.out.println("leftMax : " +arr[leftPtrForMaxVal]);
System.out.println("rightMax : "+arr[rightPtrForMaxVal]);
}
#include <iostream>
using namespace std;
int maxsum(int array[], int nlength)
{
int nfirst;
int nsecond;
if(array[0] > array[1])
{
nfirst = array[0];
nsecond = array[1];
}
else
{
nfirst = array[1];
nsecond = array[0];
}
for(int i=2; i<nlength; i++)
{
if(array[i] >= nfirst)
{
nsecond = nfirst;
nfirst = array[i];
}
}
return nfirst + nsecond;
}
int main()
{
int a[6] = {8,9,-6,0,3,9};
cout<<maxsum(a,6)<<endl;
return 0;
}
Finding firstLargest and second largest element
public static void rangeHL(int [] arr){
int firstLargestIndex=0;
int secondlargestIndex=0;
for(int i=0;i<arr.length;i++){
if(arr[i]>arr[firstLargestIndex]){
secondlargestIndex=firstLargestIndex;
firstLargestIndex=i;
}else if(arr[i]>arr[secondlargestIndex]){
secondlargestIndex=i;
}
}
}
Here is the working solution..
public static void FindStartAndEndIndexesYeildingMaxSum(int[] array)
{
//Get the first two elements into two variables
int secondLargeNumber = array[1];
int firstLargeNumber = array[0];
int startIndex = 0;
int endIndex = 1;
//start the loop from the third element
for (int i = 2; i < array.Length; i++)
{
//if the first element is less than the current element in the array, copy the current element to first element
if (firstLargeNumber <= array[i])
{
//Before copying the current element into first element, verify if first element is greater than second element..if it is copy that to second element
if (firstLargeNumber > secondLargeNumber)
{
secondLargeNumber = firstLargeNumber;
endIndex = startIndex;
}
firstLargeNumber = array[i];
startIndex = i;
}
else
{
//if first element is greater than current element,then check if current element is greater than the second element, if it is copy that to second element
if (array[i] > secondLargeNumber)
{
secondLargeNumber = array[i];
endIndex = i;
}
}
}
Console.WriteLine(String.Format("Start Index is {0} and End Index is {1} and the Sum is {2}",startIndex,endIndex,firstLargeNumber+secondLargeNumber));
Console.ReadLine();
}
Here is an implementation of Kadane's algorithm. It also handles the case where all numbers are negative.
public class MaximumSubarray {
static int arr[] = {8,9,-6,0,3,9} ;
public static void main(String args[]) {
int curr_max = arr[0];
int max_so_far = arr[0];
int index_i = 0;
int index_j = 0;
for (int i=1; i<arr.length; i++) {
if (arr[i] > curr_max + arr[i]) {
index_i = i;
}
curr_max = Math.max(arr[i], curr_max + arr[i]);
if (curr_max > max_so_far) {
index_j = i;
}
max_so_far = Math.max(curr_max, max_so_far);
}
System.out.println(max_so_far);
System.out.println(index_i);
System.out.println(index_j);
}
}
@tushar2702: have you checked your solution with an array which has +ve numbers in the beginning followed by -ve numbers. Something like int arr[] = { 8, -39, -6};.
Yes, so then my solution works for the e.g. you gave. Initialy index_i and index_j are set to 0. Within the for loop it won't satisfy any constraint and once exits index_i and index_j will remain 0. What's wrong in my solution?? correct me if i am wrong!
@tushar2702: Following is the output if arr[] = { 8, -39, -6} is used in your solution.
8
2
0
P.S: Anyways do not take it otherwise, I have seen people on careercup, who feel very offended if someone finds bug in their code and dislike the post/comment in return :). I think people should be happy that someone is taking his/her time out and going through their code. It can only be helpful.
#include<iostream>
#include<vector>
using namespace std;
int find(vector<int> v)
{
int l = v.size();
int a[l][l];
for(int i = 0; i < l; i++){
a[i][i] = v[i];
}
for(int i = 0; i < l; i++){
for(int j = i + 1; j < l; j++){
a[i][j] = a[i][j - 1]+v[j];
}
}
int max = 0;
for(int i = 0; i < l; i++){
for(int j = i; j < l; j++){
if(max < a[i][j]){
max = a[i][j];
}
}
}
return max;
}
int main()
{
vector<int> v;
int n, k;
cin >> n;
for(int i = 0; i < n; i++){
cin >> k;
v.push_back(k);
}
cout << find(v) << endl;
return 0;
}
#include<iostream>
#include<vector>
using namespace std;
int find(vector<int> v)
{
int l = v.size();
int a[l][l];
for(int i = 0; i < l; i++){
a[i][i] = v[i];
}
for(int i = 0; i < l; i++){
for(int j = i + 1; j < l; j++){
a[i][j] = a[i][j - 1]+v[j];
}
}
int max = 0;
for(int i = 0; i < l; i++){
for(int j = i; j < l; j++){
if(max < a[i][j]){
max = a[i][j];
}
}
}
return max;
}
int main()
{
vector<int> v;
int n, k;
cin >> n;
for(int i = 0; i < n; i++){
cin >> k;
v.push_back(k);
}
cout << find(v) << endl;
return 0;
}
Kadane's algorithm - Maximum Subarray Problem
- algos July 25, 2013