Amazon Interview Question
Quality Assurance EngineersCountry: United States
Do you really need a flag. reseting index would work right ?.
public static int longRunningSeq(int[] a) {
int max = Integer.MIN_VALUE;
int rcount = 0;
int startidx = 0;
int ni=0;
for(int i = 0; i < a.length; i++) {
if(a[i] < 0) {
if(rcount > max ) {
max = rcount;
startidx = ni;
}
ni=0;
rcount = 0;
} else {
if(ni==0) {
ni=i;
}
rcount++;
}
}
System.out.println(" " + startidx);
return max;
}
Before printing the result we need to compare the currLength and maxLength once again, and associate the values accordingly. Because the current snippet is missing to print the longest sequence if it comes at the end of an array.
I would propose the following solution:
(i) iterate through the elements of the array
(ii) keep track of the longest positive sequence
A sample code is shown below:
public static void findPosSeq(int a[]) {
int N = a.length;
int maxIdx = -1;
int maxLen = -1;
int len = -1;
int idx = -1;;
boolean flag = false;
for (int k = 0; k < N; k++) {
if (a[k] > 0) {
if (flag == true) {
len++;
}
else {
len = 1; // new sequence
idx = k;
flag = true;
}
}
else {
flag = false;
if (len > maxLen) {
maxLen = len;
maxIdx = idx;
}
}
}
if (maxLen > 0)
System.out.println("Length "+maxLen+", starting index "+maxIdx);
else
System.out.println("No positive sequence detected.")
}
The algoritnm is O(N) time and O(1) space complexity. After modification it should work also with stream.
there are some issues while editing.. hence posting answer again
public static void longestPositiveSequence(int[] arr) {
int index, tempIndex;
int length, tempLength;
index = tempIndex = -1;
length = tempLength = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
if (tempLength > length) {
length = tempLength;
index = tempIndex;
}
tempLength = 0;
tempIndex = i + 1;
} else {
tempLength++;
}
}
if (index != -1) {
System.out.println("Index : " + index + ", length : " + length);
} else {
System.out.println("No result found");
}
}
I think the first comment wanted to give the same logic as my code but his code is not right. I tried to use better variable naming.
class Sequence {
public void getLongestSequence(int[] input, int[] output) {
if (input.length == 0) {
output[0] = 0;//count of longest series
output[1] = 0;//starting point: 1 is the first so 0 means N/A
return;
}
int lastBegin = 0;
int lastCount = 0;
int count = 0;
int begin = 0;
boolean posEdge = input[0] > 0;
for (int i = 0; i < input.length; i++) {
if (posEdge) {
if (input[i] > 0) {
count++;
} else {
posEdge = false;
if (count > lastCount) {
lastBegin = begin + 1;
lastCount = count;
}
}
} else {
if (input[i] > 0) {
posEdge = true;
count = 1;
begin = i;
}
}
}
output[0] = lastCount;
output[1] = lastBegin;
}
}
I realized my code missed one condition, if the series ends with positive series and that is the longest series then my code does not catch it. To fix the below code should be added before the last two lines before storing output results:
if(posEdge){
if(count>lastCount){
lastBegin=begin+1;
lastCount=count;
}
}
#include <bits/stdc++.h>
using namespace std;
void LongestPositiveSequence(int a[], int n) {
int len = 0, start = 0;
for(int i = 0, from = 0, cur_len = 0; i < n; ++i)
if(a[i] <= 0) {
from = i + 1;
cur_len = 0;
}
else {
cur_len++;
if(cur_len > len) {
len = cur_len;
start = from;
}
}
printf("length %d, start index %d\n", len, start);
}
int main() {
int a[] = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
LongestPositiveSequence(a, sizeof(a) / sizeof(int));
return 0;
}
Based on Kadane's algorithm: O(n)
* one minor correction in given example: starting index is 7 and not 8
public static void findLongestPositiveSeq(int a[]) {
int currMax = 0, maxLongest = 0;
int maxStartIndex = 0, currStartIndex = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
currMax++;
} else {
maxStartIndex = i + 1;
if (currMax > maxLongest) {
maxLongest = currMax;
maxStartIndex = currStartIndex;
}
currMax = 0;
currStartIndex = i + 1;
}
}
System.out.println("max = " + maxLongest + " starting at: " + maxStartIndex);
}
Quick-and-dirty solution involving a flag with O(n) runtime:
in python:
def find_longest_sub_array(vals):
curr_start = 0
curr_sub = []
flag = False
for i in range(0,len(vals)):
if vals[i] >= 0:
if not flag:
curr_start = i
flag = True
else:
if flag:
if i - curr_start > len(curr_sub):
curr_sub = vals[curr_start:i]
flag = False
return curr_sub
adjustments to return things such as the length of the subarray or the start index are trivial.
public class LongestRunningPositiveSequenceInAnArray {
public static void main(String[] args) {
getLongestRunningPositiveSequenceInAnArray(new int[] {
1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6
});
getLongestRunningPositiveSequenceInAnArray(new int[] {
-1, -2, -3, -2, -3, -4, -6, -1, -2, -3, -4, -5, -8, -5, -6
});
getLongestRunningPositiveSequenceInAnArray(new int[] {
1, 2, 3, 2, 3, -4, -6, 1, 2, 3, 4, 5, -8, 5, 6
});
getLongestRunningPositiveSequenceInAnArray(new int[] {
1, 2, 3, 2, 3, 4, 6, 1, 2, 3, 4, 5, 8, 5, 6
});
getLongestRunningPositiveSequenceInAnArray(new int[] {
1, 2, 3, -2, 3, 4, 6, 1, 2, 3, 4, 5, 8, 5, 6
});
}
private static void getLongestRunningPositiveSequenceInAnArray(int[] arr) {
int count = 0;
int max = 0;
int indx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 0) {
count++;
} else {
if (count > max) {
max = count;
indx = i - count;
}
count = 0;
}
}
if(count > max) {
max = count;
indx = arr.length - count;
}
System.out.println("Longest Running Positive Sequence is: " + max + " Starting at index: "
+ indx);
}
}
small mistake
private static void getLongestRunningPositiveSequenceInAnArray(int[] arr) {
int count = 0;
int max = 0;
int indx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 0) {
count++;
} else {
if (count > max) {
max = count;
indx = i - count;
}
count = 0;
}
}
if(count > max) {
max = count;
indx = arr.length - count;
}
System.out.println("Longest Running Positive Sequence is: " + max + " Starting at index: "
+ indx);
}
int longestPositiveContiguousSequence(int[] a) {
if (a == null || a.length == 0) {
return 0;
}
int currLength = 0;
int maxLength = 0;
int i = 0;
while (i < a.length) {
while (a[i++] > 0) { // Count current positive sequence
currLength++;
}
if (currLength > maxLength) { // Update max sequence if needed
maxLength = currLength;
}
while (a[i++] <= 0) {} // Skip over negative sequence
}
return maxLength;
}
public class LongestPossiblePositiveSequence {
public static void main(String[] args) {
int[] arr = { 1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6 };
int[] result = getSequenceNo(arr);
System.out.println("MaxCount=" + result[1]);
System.out.println("Index=" + result[0]);
}
public static int[] getSequenceNo(int[] arr) {
int c = 0;
int maxCount = 0;
int[] result = { 0, 0 };
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
c++;
if (c > maxCount) {
maxCount = c;
result[1] = maxCount;
result[0] = i - maxCount + 1;
}
} else {
c = 0;
}
}
return result;
}
}
public static void main(String[] args) {
int arr[] = { 1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6, 7, 8, 9,
10 };
int longestRunning = 0;
int index = 0;
int run = 0;
boolean isNegativeOrLastElement = false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 0) {
run++;
if (i == arr.length - 1) {
isNegativeOrLastElement = true;
}
} else {
isNegativeOrLastElement = true;
}
if (isNegativeOrLastElement) {
index = i - run;
longestRunning = run;
run = 0;
isNegativeOrLastElement = false;
}
}
if (longestRunning > 0) {
System.out.println("Longest running array = " + longestRunning
+ " starting at index = " + index);
}
}
My proposition requires O(n) space and O(n) running time:
/**
* Created by sky on 16/04/15.
*/
public class FindLongestSequence {
public static void main(String[] args) {
//int[] arr = {1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6};
int[] arr = {1, 2, 3, 1, 2, 3, 4};
int[] tmp = new int[arr.length - 1];
for (int i = 1; i < arr.length; i++) {
tmp[i - 1] = arr[i] - arr[i - 1];
System.out.print(tmp[i - 1] + " ");
}
System.out.println();
int i = 0;
int maxRepeated = 0;
int repeated;
int idx = 0;
while (i < tmp.length) {
int j = i + 1;
repeated = 2;
while (j < tmp.length && tmp[j] == tmp[i]) {
j++;
repeated++;
}
if (repeated > maxRepeated) {
idx = i;
maxRepeated = repeated;
}
i = j;
}
idx += 1;
System.out.println(idx + " " + maxRepeated);
}
}
package src;
public class LongestPositiveSequence {
public static String largestNumberIndex(int[] inputArray)
{
int count=-1;
int max=0;
int temp=0;
int index=0;
for(int i=0;i<inputArray.length;i++)
{
temp=inputArray[i];
if(temp>0)
{
count++;
if(temp>max)
{
max=temp;
index=count;
}
}
}
String output="Largest number is: "+max+" at index: "+index;
return output;
}
public static void main(String[] args)
{
//input array
int[] inputArray={10,20,30,-45,-8,-9,88,-7};
System.out.print(largestNumberIndex(inputArray));
}
}
package src;
public class LongestPositiveSequence {
public static String largestNumberIndex(int[] inputArray)
{
int count=-1;
int max=0;
int temp=0;
int index=0;
for(int i=0;i<inputArray.length;i++)
{
temp=inputArray[i];
if(temp>0)
{
count++;
if(temp>max)
{
max=temp;
index=count;
}
}
}
String output="Largest number is: "+max+" at index: "+index;
return output;
}
public static void main(String[] args)
{
//input array
int[] inputArray={10,20,30,-45,-8,-9,88,-7};
System.out.print(largestNumberIndex(inputArray));
}
}
package src;
public class LongestPositiveSequence {
public static String largestNumberIndex(int[] inputArray)
{
int count=-1;
int max=0;
int temp=0;
int index=0;
for(int i=0;i<inputArray.length;i++)
{
temp=inputArray[i];
if(temp>0)
{
count++;
if(temp>max)
{
max=temp;
index=count;
}
}
}
String output="Largest number is: "+max+" at index: "+index;
return output;
}
public static void main(String[] args)
{
//input array
int[] inputArray={10,20,30,-45,-8,-9,88,-7};
System.out.print(largestNumberIndex(inputArray));
}
}
public class Longest_running_sequence {
public static void main(String[] args){
int[] a = {1,2,-3,2,3,4,-6,3,4,5,-8,5,6};
int length = 0;
int start_index = 0, count = 0, max_count = -1, max_index = -1;
while(length < a.length){
if(a[length] > 0) {
count++;
} else {
if(count > max_count){
max_count = count;
max_index = start_index + 1;
}
count = 0;
start_index = length + 1;
}
length++;
}
System.out.println("length: "+max_count+" index: "+max_index);
}
}
public class Longest_running_sequence {
public static void main(String[] args){
int[] a = {1,2,-3,2,3,4,-6,3,4,5,-8,5,6};
int length = 0;
int start_index = 0, count = 0, max_count = -1, max_index = -1;
while(length < a.length){
if(a[length] > 0) {
count++;
} else {
if(count > max_count){
max_count = count;
max_index = start_index + 1;
}
count = 0;
start_index = length + 1;
}
length++;
}
System.out.println("length: "+max_count+" index: "+max_index);
}
}
package com.gs.collections.kata;
public class Test {
public static void main(String[] args) {
int count=0;
int maxLength=0;
int startIndex=0;
int ar[]={1,2,3,1,-5,-6,5,-8,4,2,1,3,4,5,3,-9};
for(int i=0;i<ar.length;i++)
{
if(ar[i]<0)
{
if(count>maxLength)
{
startIndex=i-count;
maxLength=count;
}
count=0;
}
else{
count++;
}
}
System.out.println(maxLength);
System.out.println(startIndex);
}
}
package com.gs.collections.kata;
public class Test {
public static void main(String[] args) {
int count=0;
int maxLength=0;
int startIndex=0;
int ar[]={1,2,3,1,-5,-6,5,-8,4,2,1,3,4,5,3,-9};
for(int i=0;i<ar.length;i++)
{
if(ar[i]<0)
{
if(count>maxLength)
{
startIndex=i-count;
maxLength=count;
}
count=0;
}
else{
count++;
}
}
System.out.println(maxLength);
System.out.println(startIndex);
}
}
class LongestPositiveSequenceArray{
public static void main(String... a){
int [] myArray = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
//int [] myArray = {1,2,3,-1,1,2,3,4};
int index=0;
int count = 0;
int tempCount = 0;
int currentIndex = 0;
for(int i=1; i<myArray.length;i++){
if(myArray[i-1]>0 && myArray[i-1]<=myArray[i]){
if(count == 0){
currentIndex = i-1;
}
count++;
}
else{
if(tempCount < count){
tempCount = count;
index = currentIndex;
}
count =0;
}
}
if(tempCount > count){
count=tempCount;
}
else{
index = currentIndex;
}
if(count==0){
System.out.println("No sequence found!!");
}
else{
System.out.println("Sequence found with length:"+(count+1)+", at index:"+index);
}
}
}
class LongestPositiveSequenceArray{
public static void main(String... a){
int [] myArray = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
//int [] myArray = {1,2,3,-1,1,2,3,4};
int index=0;
int count = 0;
int tempCount = 0;
int currentIndex = 0;
for(int i=1; i<myArray.length;i++){
if(myArray[i-1]>0 && myArray[i-1]<=myArray[i]){
if(count == 0){
currentIndex = i-1;
}
count++;
}
else{
if(tempCount < count){
tempCount = count;
index = currentIndex;
}
count =0;
}
}
if(tempCount > count){
count=tempCount;
}
else{
index = currentIndex;
}
if(count==0){
System.out.println("No sequence found!!");
}
else{
System.out.println("Sequence found with length:"+(count+1)+", at index:"+index);
}
}
}
#include <iostream>
using namespace std;
void LongestPositiveSequence(int a[], int n) {
int length = 0, startIndex = 0, temp_length = 0;
for(int i = 0; i < n; i++)
{
if(a[i]>0)
{
temp_length++;
}
else
{
if(temp_length > length)
{
startIndex = i - temp_length;
length = temp_length;
temp_length = 0;
}
}
}
cout << "Length : " << length << " and Start index : " << startIndex << endl;
}
int main()
{
int a[] = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
LongestPositiveSequence(a, sizeof(a) / sizeof(int));
return 0;
}
#include <iostream>
using namespace std;
void LongestPositiveSequence(int a[], int n) {
int length = 0, startIndex = 0, temp_length = 0;
for(int i = 0; i < n; i++)
{
if(a[i]>0)
{
temp_length++;
}
else
{
if(temp_length > length)
{
startIndex = i - temp_length;
length = temp_length;
temp_length = 0;
}
}
}
cout << "Length : " << length << " and Start index : " << startIndex << endl;
}
int main()
{
int a[] = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
LongestPositiveSequence(a, sizeof(a) / sizeof(int));
return 0;
}
Dictionary<int, StringBuilder> dict = new Dictionary<int,StringBuilder>();
int[] arr = new int[] { 1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6 };
StringBuilder s = null;
for (int i = 0; i < arr.Length; i++)
{
if (i == 0 && arr[0] > 0)
{
s = new StringBuilder();
}
if (arr[i] < 0 )
{
int index = i - s.Length;
dict.Add(index + 1, s);
s = new StringBuilder();
}
else
{
s.Append(arr[i]);
}
}
Console.WriteLine(dict[8]);
Console.ReadLine();
Another Solution::
class LongestRunningPositiveSequence{
public static void main(String... a){
int arr[] = {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
LongestRunningPositiveSequence obj = new LongestRunningPositiveSequence();
System.out.println(obj.solution(arr));
int[] arr2 = {1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6};
System.out.println(obj.solution(arr2));
int arr3[] = {
-1, -2, -3, -2, -3, -4, -6, -1, -2, -3, -4, -5, -8, -5, -6
};
System.out.println(obj.solution(arr3));
int arr4[] = {
1, 2, 3, 2, 3, -4, -6, 1, 2, 3, 4, 5, -8, 5, 6
};
System.out.println(obj.solution(arr4));
int arr5[] = {
1, 2, 3, 2, 3, 4, 6, 1, 2, 3, 4, 5, 8, 5, 6
};
System.out.println(obj.solution(arr5));
int arr6[] = {
1, 2, 3, -2, 3, 4, 6, 1, 2, 3, 4, 5, 8, 5, 6
};
System.out.println(obj.solution(arr6));
}
int solution(int[] arr){
int len = arr.length;
int lastHighestCount = 0;
int currentCount = 0;
int lastElementOfSequence =0;
for(int i=1;i<len;i++){
if(arr[i-1] > 0 && arr[i-1] <= arr[i]){
currentCount++;
if( (i==len-1) && currentCount > lastHighestCount){
lastHighestCount = currentCount;
lastElementOfSequence = arr[i];
}
}
else if(currentCount > lastHighestCount){
lastHighestCount = currentCount;
lastElementOfSequence = arr[i-1];
currentCount=0;
}
}
return lastElementOfSequence;
}
}
public void longestRunningPositiveSequence(int[] a){
int previousLong = 1;
int nextLong = -1;
int previousIndex = 0;
int nextIndex = -1;
for (int i = 0; i < a.length; i++) {
if(a[i] > 0){
if(nextLong == -1){
nextLong = 1;
nextIndex = i;
}else{
nextLong++;
}
}else{
//negative number -- record current sequence index and length
if(previousLong < nextLong){
previousLong = nextLong;
previousIndex = nextIndex;
}
//reset indexes.
nextLong = -1;
}
}
System.out.println(previousLong+" previous starting from index: "+previousIndex);
}
int sequenceIndex=-1;
int counter = 0;
int lastMaxSeqIndex=-1;
int lastMaxSeqCount=-1;
boolean everPositiveFound = false;
for (int i=0;i<array.length;i++) {
int currentNumber = array[i];
if(currentNumber > 0){
everPositiveFound= true;
counter++;
if(sequenceIndex ==-1){
sequenceIndex = i;
}
if(i==array.length-1){
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
}else{
if((counter !=0 && sequenceIndex !=-1) && counter > lastMaxSeqCount){
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
sequenceIndex = -1;
counter=0;
}
}
int finalIndex = -1;
int finalLength = -1;
if(lastMaxSeqIndex == -1 && lastMaxSeqCount == -1 && everPositiveFound){
finalIndex = sequenceIndex;
finalLength = counter;
}else if (everPositiveFound){
finalIndex = lastMaxSeqIndex;
finalLength = lastMaxSeqCount;
}
if(everPositiveFound){
System.out.println("finalIndex["+finalIndex+"],Length["+finalLength+"]");
}else{
System.out.println("No positive number found");
}
int sequenceIndex = -1;
int counter = 0;
int lastMaxSeqIndex = -1;
int lastMaxSeqCount = -1;
boolean everPositiveFound = false;
for (int i = 0; i < array.length; i++) {
int currentNumber = array[i];
if (currentNumber > 0) {
everPositiveFound = true;
counter++;
if (sequenceIndex == -1) {
sequenceIndex = i;
}
if (i == array.length - 1) {
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
} else {
if ((counter != 0 && sequenceIndex != -1)
&& counter > lastMaxSeqCount) {
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
sequenceIndex = -1;
counter = 0;
}
}
int finalIndex = -1;
int finalLength = -1;
if (lastMaxSeqIndex == -1 && lastMaxSeqCount == -1 && everPositiveFound) {
finalIndex = sequenceIndex;
finalLength = counter;
} else if (everPositiveFound) {
finalIndex = lastMaxSeqIndex;
finalLength = lastMaxSeqCount;
}
if (everPositiveFound) {
System.out.println("finalIndex[" + finalIndex + "],Length["
+ finalLength + "]");
} else {
System.out.println("No positive number found");
}
int sequenceIndex = -1;
int counter = 0;
int lastMaxSeqIndex = -1;
int lastMaxSeqCount = -1;
boolean everPositiveFound = false;
for (int i = 0; i < array.length; i++) {
int currentNumber = array[i];
if (currentNumber > 0) {
everPositiveFound = true;
counter++;
if (sequenceIndex == -1) {
sequenceIndex = i;
}
if (i == array.length - 1) {
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
} else {
if ((counter != 0 && sequenceIndex != -1)
&& counter > lastMaxSeqCount) {
lastMaxSeqIndex = sequenceIndex;
lastMaxSeqCount = counter;
}
sequenceIndex = -1;
counter = 0;
}
}
int finalIndex = -1;
int finalLength = -1;
if (lastMaxSeqIndex == -1 && lastMaxSeqCount == -1 && everPositiveFound) {
finalIndex = sequenceIndex;
finalLength = counter;
} else if (everPositiveFound) {
finalIndex = lastMaxSeqIndex;
finalLength = lastMaxSeqCount;
}
if (everPositiveFound) {
System.out.println("finalIndex[" + finalIndex + "],Length["
+ finalLength + "]");
} else {
System.out.println("No positive number found");
}
#include<bits/stdc++.h>
using namespace std;
int longestpositive(int arr[],int n)
{
int start=0,end=0;
int maxwindow=INT_MIN,localstart=0;
while(end<n)
{
if(arr[end]>0)
{
end++;
}
else if(start<end)
{
if(arr[start]>0)
{
if(end-start>maxwindow)
{
maxwindow=end-start;
localstart=start;
}
}
start++;
}
else
end++;
}
for(int i=0;i<maxwindow;i++)
cout<<arr[localstart+i]<<" ";
cout<<endl;
return maxwindow;
}
int main()
{
int arr[]={-1,2,-3,4,5,6,-8};
int n=sizeof(arr)/sizeof(arr[0]);
cout<<longestpositive(arr,n);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int longestpositive(int arr[],int n)
{
int start=0,end=0;
int maxwindow=INT_MIN,localstart=0;
while(end<n)
{
if(arr[end]>0)
{
end++;
}
else if(start<end)
{
if(arr[start]>0)
{
if(end-start>maxwindow)
{
maxwindow=end-start;
localstart=start;
}
}
start++;
}
else
end++;
}
for(int i=0;i<maxwindow;i++)
cout<<arr[localstart+i]<<" ";
cout<<endl;
return maxwindow;
}
int main()
{
int arr[]={-1,2,-3,4,5,6,-8};
int n=sizeof(arr)/sizeof(arr[0]);
cout<<longestpositive(arr,n);
return 0;
}
public static void main(String[] args) {
int[] a = {1, 2,1,4,5,-10};
int count = 0, maxCount = 0;
int startInd = 0, endInd = 0;
for(int i=0; i<a.length; i++) {
if(a[i]>0) {
count++;
} else {
if(maxCount<count) {
startInd = i - count;
endInd = i-1;
maxCount = count;
count = 0;
}
}
}
if(maxCount<count) {
startInd = a.length - count;
endInd = a.length-1;
maxCount = count;
}
System.out.println(maxCount);
System.out.println(startInd);
System.out.println(endInd);
}
int[] a= {-1,-2,-3,4,3,-4,5,6,7,9,-9};
int count=0;
Boolean isstart=false,isend=false;
List<Integer> m = new ArrayList<Integer>();
for(int i=0;i<a.length;i++)
{
if(a[i]>0 )
{
isstart=true;
count++;
}
if(a[i]<0 && isstart==true )
{
isend=true;
isstart=false;
m.add(count);
count=0;
}
//count=0;
}
m.sort(null);
System.out.println(m.get(m.size()-1));
}
The flag is never set to true in your code. Here is the modification to your code
public class LongestPositiveSequence {
public void longestPositiveSequence(int[] a){
int maxLength = 0;
int currLength = 0;
int maxIndex = 0;
int currIndex = 0;
boolean flag = false;
for(int i = 0; i < a.length; i++){
if(a[i] > 0){
if(flag == true){
currLength++;
}
else{
currIndex = i;
currLength = 1;
flag = true;
}
}else{
if(currLength > maxLength){
maxLength = currLength;
maxIndex = currIndex;
}
flag = false;
}
}
if(maxLength > 0){
System.out.println("Max Length:" + maxLength + " || maxIndex: "+ ++maxIndex);
}
}
public static void main(String[] args){
LongestPositiveSequence sequence = new LongestPositiveSequence();
int a[] = new int[] {1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6};
sequence.longestPositiveSequence(a);
}
}
The flag needs to set to true for the first +ve no of the sequence and set to false when -ve no is encountered
- Saurabh Pandit April 15, 2015