Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
public static int getMaxSum(int[] arr)
{
int start=0;
int end=0;
int tempStart=0;
int maxSum =0;
int maxSumEnding =0;
for(int i=0;i<arr.length;i++)
{
if((maxSumEnding<0 && arr[i]<0))
{
maxSumEnding =0;
tempStart = i;
}
maxSumEnding += arr[i];
if(maxSumEnding < arr[i])
{
maxSumEnding = arr[i];
tempStart = i;
}
if(maxSumEnding > maxSum && i-tempStart >1)
{
maxSum = maxSumEnding;
end = i;
start = tempStart;
}
}
System.out.println(start);
System.out.println(end);
return maxSum;
}
How about this:
public static int[] maxSubsection(int[] arr){
if(arr == null || arr.length < 2){
return null;
}
int start = 0;
int end = 1;
int tempStart = start;
int tempEnd = end;
int localMax = arr[0] + arr[1];
int max = localMax;
int temp;
int ptr = 2;
while (ptr < arr.length){
//compute shifting local max
temp = arr[ptr-1] + arr[ptr];
if(temp < localMax + arr[ptr]){
localMax += arr[ptr];
}
else{
localMax = temp;
start = ptr-1;
}
end = ptr;
//compare with the overall max
if(localMax > max){
start = tempStart;
end = tempEnd;
max = localMax;
}
ptr++;
}
return new int[]{start, end};
}
public static int[] maxSubArrayEpic(int[] A) {
if (A.length <= 2 || A == null) {
return A;
}
int[] dp = new int[A.length];
dp[0] = A[0];
// use dp array to store the max sum of subarray
for (int i = 1; i < A.length; i++) {
dp[i] = Math.max(A[i], dp[i - 1] + A[i]);
}
int max = dp[0];
int index = 0;
// iterate dp array to find the max index;
for (int i = 1; i < dp.length; i++) {
if (dp[i] > max) {
index = i;
max = dp[i];
}
}
// use list to add the element of max subarray
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(A[index]);
if (index - 1 > 0) {
for (int i = index - 1; i >= 0; i--) {
if (dp[i] < 0) {
break;
}
list.add(A[i]);
}
}
int[] result = new int[list.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = list.get(i);
}
if (result.length == 1) {
result = new int[2];
int maxPair = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int i = 1; i < A.length; i++) {
if (A[i] + A[i - 1] > maxPair) {
start = i - 1;
end = i;
maxPair = A[i] + A[i - 1];
}
}
result[0] = A[start];
result[1] = A[end];
}
return result;
}
#include <iostream>
#include <limits.h>
using namespace std;
void kadane(int a[], int n){
int gstart=0;
int gend=0;
int lmax=0;
int gmax=INT_MIN;
for(int i=0;i<n;i++){
lmax=max(lmax+a[i],a[i]);
gmax=max(lmax,gmax);
if(gmax==a[i]){
gstart=i;
gend=i;
}
else if(gmax==lmax){
gend=i;
}
}
if(gstart==gend){
gmax=INT_MIN;
for(int i=1;i<n;i++){
gmax=max(gmax,a[i-1]+a[i]);
if(gmax==(a[i-1]+a[i])){
gstart=i-1;
gend=i;
}
}
}
cout<<gstart<<" "<<gend<<" "<<gmax<<endl;
}
int main(){
//int a[]={1,2,3,-4,5,-9};
int a[]={-1,-2,-3,-4,-5,-9};
int n=sizeof(a)/sizeof(a[0]);
kadane(a,n);
return 0;
}
Follow kadane's idea, this is my code.
This one dimensional DP problem has subproblem: Given maxsub[i], to generate largest subarray sum with at least two elements, we only consider: ``maxsub[i] + A[i]``. But to continue ``maxsub`` array, we consider both ``maxsub[i]+A[i]`` and ``A[i]``.
pair<int, int> maxSubArray(int A[], int n) {
if (n <= 1) return pair<int, int>{-1, -1};
int ret(INT_MIN), localmax(A[0]);
int ed = 0;
for (int i = 1; i < n; ++i) {
if (ret < localmax + A[i]) {
ret = localmax + A[i];
ed = i;
}
localmax = max(localmax + A[i], A[i]);
}
int sum (A[ed]), st(ed);
do {
sum += A[--st];
} while (sum != ret);
return make_pair(st, ed);
}
Playable code at
ideone.com/WMT6uZ
import java.util.*;
public class Subarray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={-1,1,10,-6,-10};
//int[] arr={-1,-2,-5,-4,-9};
int max=0,prev_max=0;
int check_mark = arr[0]+arr[1];
boolean in_negate=false;
int start_index=0,end_index=0;
int best_score=0, arr_score=0;
for(int p=0;p<arr.length;p++){
best_score+=arr[p];
}
ArrayList output_arr=new ArrayList();
ArrayList temp_arr=new ArrayList();
for(int i=0;i<arr.length-1;i++){
max+=arr[i];
temp_arr.add(arr[i]);
for(int j=i+1;j<arr.length;j++){
prev_max=max;
max+=arr[j];
if(j!=i+1){
if(max>prev_max && max>=best_score){
if(in_negate){
for(int t=start_index;t<end_index+1;t++){
temp_arr.add(arr[t]);
}
if(end_index!=j){
temp_arr.add(arr[j]);
}
start_index=0;
end_index=0;
in_negate=false;
}
else{
temp_arr.add(arr[j]);
}
}
else{
if(start_index==0 &&end_index==0){
start_index=j;
if(arr.length-1==j){
end_index=j;
}
else
{
end_index=j+1;
}
in_negate=true;
}
else
{
end_index=j;
}
}
if(max>best_score){
best_score=max;
}
else if(prev_max>best_score){
best_score=prev_max;
in_negate=false;
}
}
else{
temp_arr.add(arr[j]);
if(max>best_score){
best_score=max;
}
else if(prev_max>best_score){
best_score=prev_max;
}
}
}
for(int k=0;k<temp_arr.size();k++){
arr_score+=(Integer)(temp_arr.get(k));
}
if((check_mark<=arr_score)){
output_arr=(ArrayList) temp_arr.clone();
check_mark=best_score;
}
temp_arr.clear();
max=0;
prev_max=0;
arr_score=0;
in_negate=false;
start_index=0;
end_index=0;
}
System.out.print("\n\n\n " +output_arr);
}
}
This is based on Kadane's algo. Please correct me if I am wrong anywhere.
public class LengthOfMaxSumArray {
public static int[] getMaxSumArray(int array[]) {
int max_ending_here = 0;
int max_so_far = 0;
int max_start_index = 0;
int max_end_index = 0;
for(int i=0; i<array.length; i++) {
max_ending_here = max_ending_here + array[i];
if(max_ending_here < 0) {
max_ending_here = 0;
max_start_index = i+1;
}
if(max_so_far < max_ending_here) {
max_so_far = max_ending_here;
max_end_index = i;
}
}
int res[] = new int[max_end_index - max_start_index+1];
int j=0;
for(int i=max_start_index; i<= max_end_index; i++) {
res[j] = array[i];
j++;
}
return res;
}
public static void main(String args[]) {
int array[] = {7,4,-2,5,3,-6,8,-8};
int res[] =getMaxSumArray(array);
for(int i=0; i<res.length; i++) {
System.out.println(res[i]);
}
}
}
#include<stdio.h>
int check_all_positive(int input[],int size){
for(int i=0; i<size;i++){
if (input[i]<0)
return 0;
}
return 1;
}
int check_all_negative(int input[],int size){
for(int i=0;i<size;i++){
if(input[i]>0)
return 0;
}
return 1;
}
int sum_array_positive(int input[],int size){
int sum=0;
for(int i=0; i<size; i++){
sum=sum+input[i];
}
return sum;
}
int sum_array_negative(int input[],int size){
int sum=input[0];
for(int i=1;i<size;i++){
if(input[i]>sum)
sum=input[i];
}
return sum;
}
int Find_max_sum(int input[],int size){
int length=2,maximum=0,start_pos=0,temp_sum=0;
while(length<=size){
start_pos=0;
while(start_pos<=(size-length)){
temp_sum=0;
for(int i=start_pos;i<(start_pos+length);i++){
temp_sum=temp_sum+input[i];
}
if(temp_sum>maximum)
maximum=temp_sum;
start_pos=start_pos+1;
}
length=length+1;
}
return maximum;
}
int main(){
int input[]={-2,-3,-7,-2,-7,-4,-1,11,-1,13};
int size=sizeof(input)/sizeof(input[1]);
if(check_all_positive(input,size)){
printf("%d",sum_array_positive(input,size));
return 0;
}
if(check_all_negative(input,size)){
printf("%d",sum_array_negative(input,size));
return 0;
}
printf("%d",Find_max_sum(input,size));
}
Kandane's algo.
public class MaximumSubsequence {
public static void main(String[] args) {
maximum(new int[] { -2, -3, 4, -1, -2, 1, 5, -3 });
}
static void maximum(int a[]) {
int max_ending_here = 0;
int max_so_far = 0;
int start = 0, end = 0;
for (int i = 0; i < a.length; i++) {
max_ending_here += a[i];
if (max_ending_here < 0) {
max_ending_here = 0;
start = i + 1;
}
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
end = i;
}
}
if (end - start >= 2) {
print(a, start, end);
}
}
private static void print(int[] a, int start, int end) {
while (start <= end) {
System.out.print(a[start] + " ");
start++;
}
}
}
public class MaxSubSequence {
public static void main(String[] args) {
//maximum(new int[] { -2, -3, 4, -1, -2, 1, 5, -3 });
maximum(new int[] { 1,2,3,-7,1,1,2 });
}
static void maximum(int a[]) {
int max_ending_here = 0;
int max_so_far = 0;
int start = 0, end = 0;
int start_L =0;
for (int i = 0; i < a.length; i++) {
max_ending_here += a[i];
if (max_ending_here < 0) {
max_ending_here = 0;
start = i + 1;
}
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
start_L =start;
end = i;
}
}
if (end - start_L >= 2) {
print(a, start_L, end);
}
else
System.out.println("sub array less than 2");
}
private static void print(int[] a, int start, int end) {
while (start <= end) {
System.out.print(a[start] + " ");
start++;
}
}
}
public class LargestSumSubArray {
public static void main(String[] args) {
int [] a={1,2,-5,8,-7,2,11,-4};
int max=a[0],maxt=max;
int start=0,end=0;
int maxtemp= a[0];
for(int i=1; i< a.length; i++){
maxt=max;
maxtemp=Math.max(a[i],maxtemp+a[i]);
max=Math.max(maxtemp, max);
if(maxtemp<=a[i]){
start=i;
}
if(max>maxt)
end=i;
}
for(int j=start;j<=end;j++)
System.out.print(a[j]+" ");
System.out.println();
System.out.println(max);
}
}
#include <iostream>
using namespace std;
int largest_sum_array(int* arr,int len)
{
int i,max_so_far=arr[0],current_sum=arr[0];
for(i=1;i<len;i++)
{
current_sum=max(current_sum+arr[i],arr[i]);
max_so_far=max(current_sum,max_so_far);
}
return max_so_far;
}
int main()
{
int a[]={-1,-2,4,5};
cout<<largest_sum_array(a,4);
}
Modified Kandane's algorithm.
- Gang.Yang2012 October 05, 2014