Nagarro Interview Question
InternsCountry: India
This will not work when the input array likewise --> 2,4,5,-2,4,-4,3 correct answer is 12, your code will return 11.
package crackingCodingInterview;
public class StockTraderProfit {
public static void main(String[] args) {
int[] trades = {1,2,3,4,-2,-3,1};
int noOfTrades = 0;
int maxProfit = tradeMax(trades, noOfTrades);
System.out.println(maxProfit);
}
private static int tradeMax(int[] trades, int noOfTrades) {
// TODO Auto-generated method stub
int maxProfit = 0;
int currentProfit = 0;
for (int i = 0; i < trades.length; i++) {
currentProfit = currentProfit + trades[i];
if (currentProfit <= 0) {
currentProfit = 0;
}
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}
return maxProfit;
}
}
import java.util.Scanner;
public class Driver
{
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
int min = Integer.MIN_VALUE;
int maxProfit = 0;
String[] input = stdIn.nextLine().split(" ");
for (int i = 0; i < input.length && min < Integer.parseInt(input[i]); i++)
{
if (Integer.parseInt(input[i]) > 0)
{
maxProfit += Integer.parseInt(input[i]);
//min = Integer.parseInt(input[i]);
min = 0;
}
}
System.out.println(maxProfit);
} // end of main
} // end of class
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> Numbers;
vector<int>::iterator itr;
int N,num,i;
int MaxSum = 0, SumSofar = 0;
cout<<"Enter Numbers of integeres: "<<endl;
cin>>N;
cout<<"Enter "<<N<<" Integers"<<endl;
for(i=1;i<=N;i++){
cin >>num;
Numbers.push_back(num);
}
for(itr=Numbers.begin();itr!=Numbers.end();++itr)
cout<<*itr<<" ";
for(itr=Numbers.begin();itr!=Numbers.end();++itr){
SumSofar = SumSofar + *itr;
if(SumSofar < 0){
SumSofar = 0;
}else if(MaxSum<SumSofar){
MaxSum = SumSofar;
}
}
cout<<" "<<endl;
cout<<"Max Sum = "<<MaxSum<<endl;
return 0;
}
import java.util.*;
public class MaxProfit {
public static void main(String[] args){
int input[] = {1,2,3,4,-2,-3,1};
System.out.println(Max(input));
}
public static int Max(int array[]){
int maximum=0;
int sum[] = new int[array.length];
if(array[0] > 0){
maximum = array[0];
}
sum[0]= maximum;
for(int i = 1;i < array.length;i++){
sum[i] = array[i]+sum[i-1];
if (sum[i] > maximum){
maximum = sum[i];
}
}
return maximum;
}
}
static void findMaxProfit(int trades, int[] profitLossArray){
int sum = profitLossArray[0];
int maxSum = sum;
for(int i = 1; i<profitLossArray.length; i++) {
if((sum <0) && ((sum+profitLossArray[i])>sum)){
sum = profitLossArray[i];
}
else
sum = sum + profitLossArray[i];
if(maxSum<sum){
maxSum = sum;
}
}
System.out.println(maxSum);
}
static void findMaxProfit(int trades, int[] profitLossArray){
int sum = profitLossArray[0];
int maxSum = sum;
for(int i = 1; i<profitLossArray.length; i++) {
if((sum <0) && ((sum+profitLossArray[i])>sum)){
sum = profitLossArray[i];
}
else
sum = sum + profitLossArray[i];
if(maxSum<sum){
maxSum = sum;
}
}
System.out.println(maxSum);
}
let a = [-2 ,-3 ,-4 ,-2 ,-3 ,1];
let sum= 0;
let array = [];
for (let i = 0; i < a.length; i++) {
if(a[i] > 0) {
sum += a[i];
} else if(sum > 0) {
array.push(sum);
console.log(sum);
sum = 0;
}
}
array.push(sum);
console.log(array);
let largest = 0;
for (j=0; j<array.length; j++){
if (array[j]>largest) {
largest=array[j];
}
}
console.log(largest)
let a = [-2 ,-3 ,-4 ,-2 ,-3 ,1];
let sum= 0;
let array = [];
for (let i = 0; i < a.length; i++) {
if(a[i] > 0) {
sum += a[i];
} else if(sum > 0) {
array.push(sum);
console.log(sum);
sum = 0;
}
}
array.push(sum);
console.log(array);
let largest = 0;
for (j=0; j<array.length; j++){
if (array[j]>largest) {
largest=array[j];
}
}
console.log(largest)
O(n)
Each time current profit streak is less than zero we can assume that we should've started trading later. This means that we can assign zero to current streak and assume that we're starting trading from the next point.
- vladimir.grebennikov December 17, 2014