Kadane's Algorithm

• video: Max Sum of Subarray

  • Time Complexity: $$O(n)$$
  • code

    int kadane(vector<int>& nums) {
      if (nums.size() == 0) return 0;
      int max_current = nums[0], max_global = nums[0];
      for (int i = 1; i < nums.size(); ++i) {
          max_current = max(nums[i], nums[i]+max_current);
          max_global = max(max_global, max_current);
      }
      return max_global;
    }
    

• video: Max Sum of Rectangle

  • Time Complexity: $$O(colcolrow)$$
  • code

• Max Sum of Subarray No Larger Than K

  • Time Complexity: $$O(nlogn)$$
  • code

    int best_cumulative_sum(int ar[],int N,int K)
    {
      set<int> cumset;
      cumset.insert(0);
      int best=0,cum=0;
      for(int i=0;i<N;i++)
      {
          cum+=ar[i];
          set<int>::iterator sit=cumset.lower_bound(cum-K);
          if(sit!=cumset.end())best=max(best,cum-*sit);
          cumset.insert(cum);
      }
      return best;
    }
    

• Max Sum of Rectangle No Larger Than K

  • Time Complexity:
  • code