Maximum subarray problem
(Mylib/DynamicProgramming/max_partial_sum.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Code

#pragma once
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename T>
  T max_partial_sum(const std::vector<T> &v) {
    T t = v[0], ret = t;
    for (int i = 1; i < (int) v.size(); ++i) {
      t   = std::max(t + v[i], v[i]);
      ret = std::max(ret, t);
    }
    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/DynamicProgramming/max_partial_sum.cpp"
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename T>
  T max_partial_sum(const std::vector<T> &v) {
    T t = v[0], ret = t;
    for (int i = 1; i < (int) v.size(); ++i) {
      t   = std::max(t + v[i], v[i]);
      ret = std::max(ret, t);
    }
    return ret;
  }
}  // namespace haar_lib

Back to top page