Can we find Maximum subarray using partial sums?
Here's my Code. The time complexity is O(n) and no space is O(1) So,why don't we use this easy to implement solution ?
int ans=arr[1],sum=0,min_sum=0;
for(int i=1;i<=n;i++)
{
sum+=arr[i];
ans=max(ans,summin_sum);
min_sum=min(sum,min_sum);
}
cout<<ans<<endl;
See also questions close to this topic

Minimal maximum continuous streak of integer
Given an string(or array) a of −1s and 1s, and an integer L, I have to minimize the longest continuous streak of 1s or −1s after flipping at most L −1s to 1s or 1s to 1s.
Eg string =
111111111
, L=2String can be converted to
111111111
.The maximum continuous streak is of 1's i.e 4 which has minimized to 2 by flipping integers at 2 indexes.I could only think of brute force by flipping 1s,1s till at most L times and then finding out the minimal max length of continuous streak of 1s and 1s. I was also thinking of using Kadanes algorithm but I don't know how to implement it in this problem.
Is there an efficient way to do this ? Any help is appreciated.

Solving MaxDouble Slice Kadane's Algorithm Variation
I was trying to sharpen my skills by solving the Codality problems. I reached this one: https://codility.com/programmers/lessons/9maximum_slice_problem/max_double_slice_sum/
I actually theoretically understand the solution:
 Use Kadane's Algorithm on the array and store the sum at every index.
 Reverse the array and do the same.
 Find a point where the sum of both is max by looping over both result sets one at a time.
 The max is the max double slice.
My question is not so much about how to solve the problem. My question is about how does one imagine that this will be way in which this problem can be solved. There are atleast 3 different concepts that need to be made use of:
The understanding that if all elements in the array are positive, or negative it is a different case than when there are some positive and negative elements in the array.
Kadane's Algorithm
Going over the array forward and reversed.
Despite all of this, Codality has tagged this problem as "Painless".
My questions is am I missing something? It seems hard that I would be able to solve this problem without knowing some of these concepts.
Is there a technique where I can start from scratch and very basic concepts and work my way up to the concepts required to solve this problem. Or is it that I am expected to know these concepts before even starting the problem?
How can I prepare my self to solve such problems where I don't know the required concepts in the future?

Algorithms : solving the "selling spatulas"
Input
consists of several (up to 150) stores’ sales records. Each record starts with a line containing an integer 1≤n≤1000. The next n lines each contain a sale from that store. Each sale has the number of minutes after opening (in the range 0 to 1439) and the profit (a real number in the range [−100,100] with two digits after the decimal). The profit can be negative because sometimes you have lossleader sales where your store actually loses money. Transactions are ordered by time, and there are never two sales in the same minute. Input ends when n=0.
There is a constant cost of $0.08 per minute to keep each store running while it is open, and you assume there are no costs associated with keeping a store closed.
Output
For each store, print the maximum profit, followed by the beginning and ending minutes when the profit is realized. If two different periods both have the maximum profit, then choose the shortest one, and if there are still ties, choose the period that starts earliest. If the store never can turn a profit, print no profit. Stores must open and close on minute boundaries.My first thought was to use kadane's idea, here is my code:
#include <iostream> #include <vector> #include <iomanip> #define CPH 0.08 //cost per hour using namespace std; struct sale{ long minute;//number of minutes after opening [0, 1439] double profit;//profit [100, 100] }; struct data { long start;//the beginning of the period long end;//the end of the period double profit;//the profit made during the period from start to end }; int main(void){ ios::sync_with_stdio(false); cin.tie(NULL); cout << std::setprecision(2); cout << std::fixed; long n; while ( (cin>>n)&&n ){ vector<sale> sales(n); for(long i=0;i<n;++i){ cin >> sales[i].minute >> sales[i].profit; } data local; //will hold local maximum period local.start = sales[0].minute; local.end = sales[0].minute; local.profit = sales[0].profit  CPH; data global(local);//will hold the global maximum period for(long i=1;i<(long)sales.size();++i){ //should we continue opening the store? double addit = local.profit+sales[i].profit  (double)(sales[i].minutesales[i1].minute)*CPH; //or should we start from here? double dontaddit = sales[i].profit  CPH; //which one is more profitable if ( dontaddit >= addit ){ local.start = sales[i].minute; local.end = sales[i].minute; local.profit = dontaddit; } else { local.end = sales[i].minute; local.profit=addit; } if( local.profit > global.profit ){ global = local; } else if ( local.profit == global.profit ){ //if same profit choose the shorter period if ( local.endlocal.start <= global.endglobal.start ) global = local; //if same period length, choose the one that starts earlier else if ( local.endlocal.start == global.endglobal.start){ if ( local.start <= global.start ) global = local ; } } } //time to decide if ( global.profit>0 ) cout << global.profit << " " << global.start << " " << global.end<<endl ; else cout << "no profit" <<endl; } return 0 ; }
Example3 1 50 2 5 3 50 94.76 1 3 0
My code passes the first 2 test files but I have been struggling all day to pass the third test file in vain.
Here is the link to the judge: https://open.kattis.com
The issue is that I got a Wrong answer on the third test file.
Any hints?