Deshaw Inc Interview Question
Country: India
Interview Type: In-Person
// code for finding max sum :
#include<iostream>
using namespace std;
int max(int a,int b)
{
return (a>b ? a :b);
}
int func(int arr[],int n,int m)
{
int maxsum;
int incl[n];
int excl[n];
incl[0] = arr[0];
excl [0] = 0;
for(int i=1;i<n;i++)
{
if(i-m-1 >=0)
{
incl[i] = max(incl[i-m-1],excl[i-m-1]) + arr[i];
}
else
incl[i] = arr[i];
excl[i] = max(excl[i-1],incl[i-1]);
maxsum = max(maxsum,max(incl[i],excl[i]));
}
return maxsum;
}
int main(){
int arr[] = {13,4,-2,1,-2,8,6,-3,5};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 2;
cout<< func(arr,n,m);
}
public class FindSequence {
public static void main(String []args){
int []arr={-9, -9, 9,4, 4, -2, 1, -2, 4, 6, -3, 5,7,-2,-3};
int m=2;
int max=0;
int min=Integer.MAX_VALUE;
int len=2;
int minStartIndex=0;
int maxStartindex=0;
for(int i=0; i<arr.length;i++){
int currentSum=0;
if((i+len)<=arr.length){
for(int j=i;j<i+len;j++){
currentSum=currentSum+arr[j];
}
}
if(max<currentSum){
max=currentSum;
maxStartindex=i;
}else if(min>currentSum){
min=currentSum;
minStartIndex=i;
}
}
System.out.println("Max: "+max+", Max Index: "+maxStartindex);
System.out.println("Min: "+min+", Min Index: "+minStartIndex);
}
}
public class FindSequence {
public static void main(String []args){
int []arr={-9, -9, 9,4, 4, -2, 1, -2, 4, 6, -3, 5,7,-2,-3};
int m=2;
int max=0;
int min=Integer.MAX_VALUE;
int len=2;
int minStartIndex=0;
int maxStartindex=0;
for(int i=0; i<arr.length;i++){
int currentSum=0;
if((i+len)<=arr.length){
for(int j=i;j<i+len;j++){
currentSum=currentSum+arr[j];
}
}
if(max<currentSum){
max=currentSum;
maxStartindex=i;
}else if(min>currentSum){
min=currentSum;
minStartIndex=i;
}
}
System.out.println("Max: "+max+", Max Index: "+maxStartindex);
System.out.println("Min: "+min+", Min Index: "+minStartIndex);
}
}
{{public class FindSequence {
public static void main(String []args){
int []arr={-9, -9, 9,4, 4, -2, 1, -2, 4, 6, -3, 5,7,-2,-3};
int m=2;
int max=0;
int min=Integer.MAX_VALUE;
int len=2;
int minStartIndex=0;
int maxStartindex=0;
for(int i=0; i<arr.length;i++){
int currentSum=0;
if((i+len)<=arr.length){
for(int j=i;j<i+len;j++){
currentSum=currentSum+arr[j];
}
}
if(max<currentSum){
max=currentSum;
maxStartindex=i;
}else if(min>currentSum){
min=currentSum;
minStartIndex=i;
}
}
System.out.println("Max: "+max+", Max Index: "+maxStartindex);
System.out.println("Min: "+min+", Min Index: "+minStartIndex);
}
}}}
- Arun Kumar Gupta August 17, 2016